并查集

2020-05-31

并查集

并查集是一种很有意思的数据结构，在某些特殊的情景下，并查集相当好用，而且掌握它也十分简单，适合新手学习。

题目

题目链接

题目大意是，一个教室里有N个学生，老师要点n次名，每次点两个人，点到的两个人成为好基友，好基友的好基友也是自己的好基友，如此一来便有了基友群，这种点名可能会出现多个基友群，老师现在想知道人数最多的基友群有多少人。

思路

当两个人成为基友的时候，先决定一个主攻；当两个基友群合并的时候，保留一个主攻。当然，一开始的时候，可以认为每个人都是一个基友群的，只是只有一个人，所以就只有一种情况了。

每次有基友群合并时，记录最大的人数。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 10000020;

//fa表示父节点， val表示节点的权值
int n, val[N], fa[N], x, y;

//先初始化， fa一开始指向自身， val一开始都为1， 因为一开始只有自己
//还有就是， init写了记得要用， 我本身老是写了但是忘了用
void Init() {
    for (int i = 1; i < N; i++) {
        val[i] = 1;
        fa[i] = i;
    }
}


//查找父节点， 注意fa[x] = Find(fa[x])， 前面一定要加fa[x] = ， 路径压缩一下， 不然会超时
//路径压缩会把多级结构压缩成一级， 避免了每次查找过程中不必要的耗时
//建议画图理解
//这一步是整个并查集的精髓所在，初学者可以细品
int Find(int x) {
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}

int main () {
    while (cin >> n) {
        Init();
        int ans = 1;
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &x, &y);
            x = Find(x);    y = Find(y);
            if (x != y) {   //如果x和y不在一个集合里面，就合并x和y所在的集合
                val[y] += val[x];
                fa[x] = fa[y];
                ans = max(ans, val[y]);
            }
        }
        cout << ans << endl;
    }
    return 0;
}