什么是并查集?

并查集是一种树型的数据结构,常用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。

并查集可以高效的进行如下操作:

  • 合并两个不相同的集合
  • 判断两个元素是否属于同一个集合

并查集常见操作

init()初始化所有元素独立为一个集合(即父节点是自身)

  • 定义数组fa[],fa[x]存储x的父节点。
  • 初始化所有元素的父节点为-1,若fa[x]=-1则代表元素x自身为一个集合。
1
2
3
void init(){
    memset(fa,-1,sizeof(fa));//
}

find()查找元素所在的集合返回根节点

  • 如果x独立为一个集合,返回x,否则返回fa[x]。

    1
    2
    3
    4
    
    int find(int x){
      if(fa[x]==-1) return x;
      return find(fa[x]);
    }
    

    unite(x,y)合并两个不相同的集合

  • 先找到x和y的代表元素。

  • 如果相同,则说明x和y已经属于同一个集合,不用处理。

  • 如果不同,将一个代表元素指向另一个代表元素。

1
2
3
4
5
6
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    fa[x]=y;
}

same(x,y)判断两个元素是否属于同一个集合

  • 分别找到x和y的代表元素。

  • 如果相同,说明x和y属于同一个集合。

    1
    2
    3
    
    bool same(int x,int y){
      return find(x)==find(y);
    }
    

并查集的优化

路径压缩

寻找父节点是采用递归的方法,不采取任何判断的合并,树有可能会退化成一条链,每次find都会是O(n)的复杂度。所以必须进行路径压缩。在我们找到根节点的时候,直接把根节点作为它的父节点。

1
2
3
4
int find(int x){
    if(fa[x]==-1) return x;
    return fa[x=]find(fa[x]);
}

按树的高度合并

合并时将元素所在深度低的集合合并到元素所在深度高的集合。

  • 定义一个deep[]数组,默认只有一个节点的集合深度为0;
  • 在unite()操作中,判断x和y的高度,将高度小的树连接到另一颗树的根节点上。
1
2
3
4
5
6
void unite(int x,int y){

    x=find(x);
    y=find(y);
    if(x==y) return;
    if(deep[x]

优化后的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int fa[N],deep[N];
void init(){
    memset(fa,-1,sizeof(fa));
    memset(deep,0,sizeof(deep));
}
int find(int x){
    if(fa[x]==-1) return x;
    return fa[x=]find(fa[x]);
}
void unite(int x,int y){

    x=find(x);
    y=find(y);
    if(x==y) return;
    if(deep[x]