并查集
并查集是一种树形数据结构，经常用于处理集合之间的操作（如元素查找、集合合并。
并查集初始化
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;
}
|
路径压缩