并查集

#include <iostream>
using namespace std;

const int N = 105;
int fa[N];  // fa[x] = x的父节点

// 查找x所在集合的根（带路径压缩）
int find(int x) {
    if (fa[x] == x)         // 如果x就是根
        return x;           // 返回根
    return fa[x] = find(fa[x]);  // ⭐ 路径压缩：递归找根，同时把x直接连到根
    // 等价于：fa[x] = find(fa[x]); return fa[x];
}

// 合并x和y所在的集合
void merge(int x, int y) {
    fa[find(x)] = find(y);  // 把x的根连到y的根上
}

int main() {
    int n;  // 节点数
    cin >> n;

    // 初始化：每个节点自成一个集合
    for (int i = 1; i <= n; i++)
        fa[i] = i;          // 每个节点的父节点是自己（自己是根）

    // 示例：合并操作
    merge(1, 2);   // 合并1和2
    merge(3, 4);   // 合并3和4
    merge(2, 4);   // 合并2和4 → 现在1,2,3,4都在同一集合

    // 查询：1和3是否在同一集合？
    if (find(1) == find(3))
        cout << "1和3在同一集合" << endl;
    else
        cout << "1和3不在同一集合" << endl;

    return 0;
}

// 输入n个人，m对好友关系，输出朋友圈个数
int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) fa[i] = i;  // 初始化

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        merge(a, b);  // 合并好友
    }

    // 统计有多少个不同的根（即朋友圈个数）
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (fa[i] == i)  // 如果i是根
            cnt++;        // 这是一个独立的朋友圈
    }
    cout << cnt << endl;  // 输出朋友圈个数
}