并查集
并查集是什么
并查集是一种用来管理元素分组情况的数据结构,并查集可以高效地进行如下操作：
查询元素a和元素b是否属于同一组
-
合并元素a和元素b所在组
并查集可以做什么
并查集的结构
并查集也是使用树形结构实现的
并查集的结构
并查集支持的操作
-
合并从一个组的根向另一个组的根连边，这样两棵树变成了一棵树，也就把两个组合并为一个组了。
并查集——合并 -
查询
如果两个节点的根相同，就可以知道它们属于同一组。
并查集——查询
并查集实现中的注意点
在树形数据结构中，如果发生了退化的情况，复杂度就会变得很高。在并查集中，可以按照如下方法避免退化：
-
对于每棵树，记录这棵树的高度，合并时如果两棵树的高度不同，从高度小的向高度大的连边
考虑了高度的合并 -
路径压缩
在查询过程中向上经过的所有的节点，都改为直接连到根上
路径压缩
代码实现
//initial the sets
void init(){
for(int i = 0; i < N; i++){
p[i] = i;
}
}
//Find(x) return the root of x
int Find(int x){
if(x == p[x]) return x;
else return p[x] = Find(p[x]);
}
//Union(x, y) union the sets of x and y
void Union(int x, int y){
int xRoot = Find(x);
int yRoot = Find(y);
if(xRoot == yRoot) return;
if(r[xRoot] < r[yRoot]) p[xRoot] = yRoot;
else if(r[xRoot] > r[yRoot]) p[yRoot] = xRoot;
else{
p[yRoot] = xRoot;
r[xRoot]++;
}
}
bool sameRoot(int x, int y){
//printf("root of %d: %d\n", x, Find(x));
//printf("root of %d: %d\n", y, Find(y));
return Find(x) == Find(y);
}
例题
- poj1182 食物链（中等）
- hdoj1213（简单）
- hdoj1272（简单）
