并查集 | find & union

并查集 Disjoint Set

b站大佬的讲解视频
以下截屏来自⬆️讲解视频

应用

检查无向图中是否有环

Kruskal算法（最小生成树）

例

1107 Social Clusters (30 分)

⚠️ 每个集合的root可能还没有收敛到同一个。因此需要遍历，调用_find函数，找到唯一的root。isRoot也用作计数当前集合的所有成员数量。isRoot数组非零元素数量即disjoint集合数量。
⚠️ greater<>()需要 #include <functional>
⚠️ sort范围，输出范围！！！

#include <cstdio>
#include <algorithm>
#include <functional>

using namespace std;
int father[1010], hobby_root[1010], nn;
int isRoot[1010];

int _find(int curr) {
    return father[curr] < 0 ? curr : father[curr] = _find(father[curr]);
}

void _union(int a, int b) {
    a = _find(a);
    b = _find(b);
    if (a != b) {
        father[a] += father[b];
        father[b] = a;
    }
}

int main() {
    scanf("%d", &nn);
    fill(father, father + 1010, -1);
    fill(hobby_root, hobby_root + 1010, 0);
    fill(isRoot, isRoot + 1010, 0);
    for (int i = 1; i <= nn; ++i) {
        int cnt, hobby;
        scanf("%d:", &cnt);
        for (int j = 0; j < cnt; ++j) {
            scanf("%d", &hobby);
            if (hobby_root[hobby] == 0) { //is 0
                hobby_root[hobby] = i;
            } else {
                _union(hobby_root[hobby], i);
            }
        }
    }
    int size = 0;
    for (int i = 1; i <= nn; ++i) {
        isRoot[_find(i)]++;
    }
    for (int i = 1; i <= nn; ++i) {
        if (isRoot[i])
            size++;
    }
    sort(isRoot, isRoot + nn + 1, greater<>());
    printf("%d\n", size);
    for (int i = 0; i < size; ++i) {
        printf("%d", isRoot[i]);
        if (i + 1 < size) printf(" ");
    }
    /*
    sort(isRoot + 1, isRoot + nn + 1, greater<>());
    printf("%d\n", size);
    for (int i = 1; i <= size; ++i) {
        printf("%d", isRoot[i]);
        if (i < size) printf(" ");
    }
     */
    return 0;
}