并查集 - OI Wiki

应用

1. 合并两个集合
2. 查询两个元素的祖宗节点
3. 计算连通分量

引入

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

顾名思义，并查集支持两种操作：

• 合并（Union）：合并两个元素所属集合（合并对应的树）
• 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。

初始化

初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。

查询

我们需要沿着树向上移动，直至找到根节点。

路径压缩

查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询。

合并

要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。

启发式合并

合并时，选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。
我们可以将节点较少或深度较小的树连到另一棵，以免发生退化。

删除

要删除一个叶子节点，我们可以将其父亲设为自己。为了保证要删除的元素都是叶子，我们可以预先为每个节点制作副本，并将其副本作为父亲。

移动

与删除类似，通过以副本作为父亲，保证要移动的元素都是叶子。

代码

没有删除、移动 操作

java

public class Main {  
    static int[] fa;  
    static void init(int n) {  
        fa = new int[n];  
        for (int i = 0; i < n; i++) {  
            fa[i] = i;  
        }  
    }  
    //找到x的根节点  
    static int find(int x) {  
        return x == fa[x] ? x : (fa[x] = find(fa[x]));  
    }  
    //合并两个节点  
    static void union(int x, int y) {  
        fa[find(x)] = find(y);  
    }  
    //计算连通分量  
    static int getConnected(int n) {  
        int cnt = 0;  
        for(int i = 0; i < n; i++) {  
            if(find(i) == i) {  
                cnt++;  
            }  
        }  
        return cnt;  
    }  
    public static void main(String[] args) {  
        init(10);  
        union(1,2);  
        union(3,5);  
        System.out.println(getConnected(10));  
    }  
}

go

package main  
  
import "fmt"  
  
type UnionFind struct {  
   parent []int  
}  
  
// NewUnionFind 集合初始化
func NewUnionFind(n int) UnionFind {  
   fa := make([]int, n)  
   for i := range fa {  
      fa[i] = i  
   }  
   return UnionFind{fa}  
}  
  
// Find 寻找根节点(带压缩)
func (u *UnionFind) Find(x int) int {  
   if u.parent[x] != x {  
      u.parent[x] = u.Find(u.parent[x])  
   }  
   return u.parent[x]  
}  
  
// Merge 合并
func (u *UnionFind) Merge(x, y int) {  
   rx := u.Find(x)  
   ry := u.Find(y)  
   if rx != ry {  
      u.parent[rx] = u.parent[ry]  
   }  
}  
  
// Same 判断是否在同一集合(在合并操作之后父亲节点不一定是根节点,不能直接比较)
func (u *UnionFind) Same(x, y int) bool {  
   return u.Find(x) == u.Find(y)  
}  
  
func Main() {  
   u := NewUnionFind(10)  
   fmt.Println(u.Find(2))  
}