并查集

并查集

并查集是什么

并查集是一种用来管理元素分组情况的数据结构,并查集可以高效地进行如下操作：

• 查询元素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（简单）