并查集
并查集是一种树形数据结构，经常用于处理集合之间的操作（如元素查找、集合合并。
n元素，m次查询
复杂度：O(m)，最坏复杂度：O（mlogn)
并查集初始化
1
2
3
4
5
6
| void init(int n) {
for(int i = 1; i <= n; i++) {
fa[i] = i;
sz[i] = dep[i] = 1;
}
}
|
集合合并
讲元素x,y所在的集合合并。
首先先找到 x,y 对应的代表元 （fa 等于自己的元素）
将其中一个代表元的 fa 指向另外一个，那么原来在这个代表元下的所有元素的代表元都会指向另外一个。
1
2
3
4
5
6
7
8
9
10
11
| int Findset(int x) {
if(fa[x] == x) return x;
return Findset(fa[x]);
}
void Union(int x,int y) {
int fx = Findset(x),fy = Findset(y);
if(fx == fy) return;
fa[fx] = fy;
}
|
路径压缩
通过缩短并查集的路径，具体是查询过程中，把沿途的每个节点的 fa 都设为集合代表元。
1
2
3
4
5
| int Findset(int x) {
if(x == fa[x]) return x;
fa[x] = Findset(fa[x]);
return fa[x];
}
|
或者
1
2
3
| int Findset(int x) {
return x == fa[x] ? x : (fa[x] == Findset(fa[x]));
}
|
启发式合并
合并两个集合优化的方法。
在合并集合的时候，我们尽量选择包含元素个数少的集合，将它合并到另一个集合中，使需要改变代表元的元素数量尽可能少。
小集合合并到较大集合称为启发式合并。
时间复杂度：log
1
2
3
4
5
6
7
8
| void Union(int x,int y) {
int fx = Findset(x),fy = Findset(y);
if(fx == fy) return;
if(sz[fx] > sz[fy])
std::swap(fx,fy);
fa[fx] = fy;
sz[fy] += sz[fx];
}
|
按深度合并
深度小的集合合并到深度大的一方。
时间复杂度：log
路径压缩过程中，有可能破坏我们维护的深度值，但总体复杂度不会差。
1
2
3
4
5
6
7
8
9
| void Union(int x,int y) {
int fx = Findset(x),fy = Findset(y);
if(fx == fy) return;
if(dep[fx] > dep[fy])
std::swap(fx,fy);
fa[fx] = fy;
if(dep[fx] == dep[fy])
dep[fy]++;
}
|