并查集

叔叔我啊

ACM树

发布于：2021年2月14日

字数：228字

时长：1分钟

次浏览

作用

寻找两个点是否联通
求最小生成树。

例题

每个人都知道自己的领导，问谁是最终的领导。
计算圈子总个数

思路

常规思路

递归寻找上级，由上级再次寻找。直到无法找到上级为止。

常用于在单树中寻找最高节点。
路径压缩

孙节点和父节点直接挂载在爷节点之下。

常用于计算不连通的树的个数。

代码

#include<iostream>
#include<cstdio>

using namespace std;

int pre[1000];

int unionSearch(int root) {
    int son, tmp;
    son = root;
    while (root != pre[root])
        root = pre[root];
    while (son != root) {
        tmp = pre[son];
        pre[son] = root;
        son = tmp;
    }
    return root;
}

int main() {
    int num, road, total, i, start, end, root1, root2;
    while (cin >> num >> road) {
        total = num - 1;
        for (i = 1; i <= num; ++i)
            pre[i] = i;
        while (road--) {
            cin >> start >> end;
            root1 = unionSearch(start);
            root2 = unionSearch(end);
            if (root1 != root2) {
                pre[root1] = root2;
                total--;
            }
        }
        printf("%d\n", total);
    }
    return 0;
}