L2-024 部落 c++ 并查集

1. 并查集的使用：https://blog.csdn.net/weixin_51995229/article/details/124313167?spm=1001.2014.3001.5501
2. 此题需要求所有部落的人数，那么用一个set集合去放所有的人即可，在初始化f数组时，我们不知道总人数的个数，可以直接初始化到最大值；
3. 求不相交的部落的个数，就是连通分量数，以及两个人是否有关系，可以参考这个题的分析：https://blog.csdn.net/weixin_51995229/article/details/124343319?spm=1001.2014.3001.5501

#include "bits/stdc++.h"

using namespace std;
set s;//用来统计部落的总人数
int f[10010];

void init() {
    for (int i = 1; i < 10010; ++i) {
        f[i] = i;
    }
}

int find(int x) {
    if (x == f[x])
        return x;
    return f[x] = find(f[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    f[x] = f[y];
}

int main() {
    int n, k, t;
    cin >> n;
    init();
    for (int i = 1; i <= n; i++) {
        cin >> k;
        //让第一个人与后面每个人建立关系即可
        int x;
        cin >> x;
        s.insert(x);
        k--;
        while (k--) {
            cin >> t;
            s.insert(t);
            merge(x, t);
        }
    }
    //计算连通块数
    int cnt = 0;//互不相交部落的个数，也就是根节点的个数
    for (int i = 1; i <= s.size(); ++i) {
        if (find(i) == i)
            cnt++;
    }
    cout << s.size() << " " << cnt << endl;
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        if (find(a) == find(b))
            cout << "Y" << endl;
        else
            cout << "N" << endl;
    }
    return 0;
}