树形数据结构（一） 并查集（Union-find）

• 概念
• • 结构
  • 并查集的初始化
  • f i n d ( ) find() find()
  • m e r g e ( ) merge() merge()
• 优化
• • 路径压缩
  • 按秩合并

并查集是一种树形数据结构，主要用于解决元素的分组问题，管理一系列不相交的集合，它支持两种操作：

• 合并：将两个不相交的集合合并为一个集合
• 查询：查询元素所在集合

并查集的一个节点只需要存储它的父节点，即可通过父节点递归寻找到根节点，因此并查集只需要一个一维数组即可实现

并查集使用一个元素代表整个集合，如图，对于只有一个元素的集合，代表元素即为它本身。

初始化一个元素的代码如下

parent[i] = i;

因此初始化 n n n个元素的代码如下

void init(int n) {
    for(int i = 0; i 

    
     
      
       
        f
       
       
        i
       
       
        n
       
       
        d
       
       
        (
       
       
        )
       
      
      
       find()
      
     
    find() 

    
     
      
       
        f
       
       
        i
       
       
        n
       
       
        d
       
       
        (
       
       
        )
       
      
      
       find()
      
     
    find()函数的作用是查询一个元素所在的集合，也即代表元素。我们采用递归的方式查找节点的父亲节点，直到找到根节点。代码如下
 
int find(int x) {
    if(parent[x] == x)
        return x;
    else
        return find(parent[x]);
}
 

    
     
      
       
        m
       
       
        e
       
       
        r
       
       
        g
       
       
        e
       
       
        (
       
       
        )
       
      
      
       merge()
      
     
    merge() 
合并两个集合的方式为，找到两个集合的代表元素，再将其中一个元素的父节点设为另一个元素即可，实现代码为
 
void merge(int i, int j) {
    parent[find(i)] = find(j);
}
 
优化 
路径压缩 
简单的并查集效率很低，如果我们对一个并查集进行多次
    
     
      
       
        m
       
       
        e
       
       
        r
       
       
        g
       
       
        e
       
       
        (
       
       
        )
       
      
      
       merge()
      
     
    merge()操作时，树会逐渐退化成链表，查询的复杂度也会逐渐变为
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)。如果我们只关心元素的根节点，在查询的过程中，将沿途每个节点的父节点都设为根节点，就可以达到优化效果，优化后的
    
     
      
       
        f
       
       
        i
       
       
        n
       
       
        d
       
       
        (
       
       
        )
       
      
      
       find()
      
     
    find()函数如下
 
int find(int x) {
    if(x == parent[x])
        return x;
    else {
        parent[x] = find(parent[x]);
        return parent[x];
    }
}
 
按秩合并 
路径压缩只在查询时进行，也只压缩一条路径，并查集的结构仍会比较复杂，我们可以记录节点的父节点的同时记录该树的深度，当进行合并操作时，由深度较大的树合并深度较小的树，代码如下
 
void merge(int i, int j) {
    int parent_i = find(i), parent_j = find(j);
    if(height[i]>=height[j])
        parent[parent_j] = parent_i;
    else if(height[j]>height[i])
        parent[parent_i] = parent_j;
    else if(i != j)
        height[parent_i]++;
}