并查集是一种用途广泛的数据结构，能够快速地处理集合的合并和查询问题，并且实现起来非常方便，在很多场合中都有着非常巧妙的应用。本文首先介绍并查集的定义、原理及具体实现，然后结合hihocoder以及poj上的题目做一些具体实践。

定义和原理

并查集(Union-Find Set)是一种树型的数据结构，其保持着用于处理一些不相交集合（ Disjoint Sets ）的合并及查询问题。有一个联合-查找算法（ union-find algorithm ）定义了两个操作用于此数据结构：

• Find 确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• Union 将两个子集合并成同一个集合。

因为它支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法， MakeSet，用于建立单元素集合。有了这些方法，许多经典的划分问题可以被解决。

网络上有两篇帮助理解的博文，博主用通俗易懂的语言，图文并茂的方式将并查集生动形象得阐释了。特附上博文链接：

• 通俗易懂的诠释并查集
• 图文并茂的解释并查集

代码实现

• 并查集的数据存储 $O(N)$

  1#define LENMAX 1000000
  2int father[LENMAX]
  

  `
  虽然并查集是树型的数据结构，但是实际的存储是用数组，就跟堆排序一样。

• 并查集的初始化MakeSet

  1void MakeSet(){
  2    int i;
  3    for(i=0;i<LENMAX;i++){
  4        father[i]=i;
  5    }
  6}
  

  MakeSet是并查集的初始化函数，这里采用father[i]==i` 来判定该 i 是否是某个集合的代表。

• 并查集的查找操作 $O(\alpha(N))[\alpha(N)<N]$

   1// 查找操作--未压缩路径
   2int Find(int x){
   3    if(x==father[x])
   4      return x;
   5    else
   6      return Find(father[x]);
   7}
   8
   9// 查找操作--压缩路径
  10int Find(int x){
  11    if(x==father[x])
  12      return x;
  13    else{
  14        father[x]=Find(father[x]);
  15        return father[x];
  16    }
  17}
  

  `
  压缩路径可以避免重复查找，其实际的意义是将树的深度由 n 变成 1 。就是将层层的等级制度变成全部向皇帝/代表负责。

• 并查集的合并操作 $O(\alpha(N))[\alpha(N)<N]$

   1// 合并操作
   2void Union(int x, int y){
   3    int fatherX = Find(x);
   4    int fatherY = Find(y);
   5
   6    // fatherY归fatherX管了
   7    if(fatherX!=fatherY)
   8      father[fatherY]=fatherX;
   9
  10    /*
  11    // 合并的时候取小的数值
  12    if(fatherX<fatherY)
  13        father[fatherY]=fatherX;
  14    else
  15        father[fatherX]=fatherY;
  16    */
  17}
  

  `

解题报告

• HihoCoder

  1. 第十四周： 无间道之并查集 | 源码

     注意点：

     1. 通过 map 将名称转化为 int 标号
     2. 最后一步判定两个名称是否是同一个集合时用 Find(mapName[nameX])==Find(mapName[nameY]) ,不能用father[mapName[nameX]]==father[mapName[nameY]]。

• POJ

  1. 1611: The Suspects | 源码

     注意点:

     1. 判定i是否和0同一类必须得通过Find找到最高的根节点是相同[代码实现可以添加rank[LENMAX]来记录同集合的元素个数]

  2. 2524: Ubiquitous Religions | 源码

     注意点：

     1. 通过 i=father[i] 判断是否是根节点,也就是说是否是一个集合

参考文献

1. 维基百科之并查集