1 基本介绍
并查集是一种用来判断两个元素之间是否有关系的集合。
它的基本思想为：对于两个元素，如果他们之间有关系，则将其连接，以此形成一颗树。
对于任意两个节点，如果它们有相同的根节点，则它们之间有关系。
2. 建立步骤
给定n个点，以及m个关系。
1. 初始状态
将每个节点的根节点都指向自己
for (int i = 0; i < n; i++) {
pre[i] = i;
}
2. 建立关系
对于给定的两个节点，我们发现，如果要连接两个节点所在的树，只能改变根节点。所以，我们先构建方法寻找根节点，再将一颗树的根节点连接到另一棵树的根节点上。
int find(int x) {
//1. 递归方式
return pre[x] == x ? x : find(pre[x])
//2. 非递归
while(pre[x]^x) x = pre[x];
return x;
}
连接函数
void merge(int x, int y) {
x = find(x), y = find(y);
pre[x] = y;
}
例题分析
来源：洛谷P3367
1. 并查集（无优化）
#include <iostream>
using namespace std;
const int N = 10e5 + 9;
int pre[N];
int find(int x) {
while (pre[x] ^ x) x = pre[x];
return x;
}
void merge(int x, int y) {
x = find(x), y = find(y);
pre[x] = y;
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < N; i++) pre[i] = i;
while (m--) {
int z, x, y;
cin >> z >> x >> y;
if (z == 1) {
merge(x, y);
} else {
cout << (find(x) == find(y) ? 'Y' : 'N') << "\n";
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
while (_--) solve();
return 0;
}
2. 路径压缩
当我们每一次查找x的根节点的时候，顺便将x的父节点的根节点也变成根节点，使得生成的树的形状又矮又胖。
只需要修改find函数
int find(int x) {
return pre[x] == x ? x : pre[x] = find(pre[x]);
}
或者为使用两次while循环来改变。
3. 按秩合并
由上面的分析我们知道，如果是将一颗小树附加到一颗大树上面，那么在查找的过程中的复杂度会降低，以此，我们构建一个rank数组，初始值都为1，它记录这棵树的层数（只有根节点的数有效，毕竟我们只连接根节点）
注意，当我们使用按秩合并的时候，我们在查找的时候就不能进行路径压缩（这样会导致秩不断在改变，我尝试了一下一起使用，效果反而不如单个使用）。
修改的merge函数为：
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (rnk[x] >= rnk[y]) pre[y] = x, rnk[x]++;
else
pre[y] = x, rnk[y]++;
}
4. 按大小合并
和秩一样，当一颗较小的树合并到另一棵较大的树的时候，形成的树会变得矮胖。因此，创建一个siz数组来储存每棵树的大小，初始值为1。和上面一样，只需要修改为：
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (siz[x] >= siz[y]) pre[y] = x, siz[x] += siz[y];
else
pre[y] = x, siz[y] += siz[x];
}