并查集——一种不相交集合的问题的数据结构

1. 并查集

1.1.并查集的定义

在[计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：

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

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

Tao：从上*的定义。通俗的讲，并查集就是用于：查询元素所属集合、两个元素是否是同一个集合、合并两个集合。所以就是处理不相交集合之间的一些问题。

并查集主要有两个操作：

find:查找元素属于哪个集合。

union:合并两个集合成一个集合。

另外，MakeSet就是初始化操作，将每个元素初始化为一个单元素集合。

1.1.1. 集合的表示

为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，Find(x) 返回x所属集合的代表，而Union使用两个集合的代表作为参数。

1.1.1.1.并查集森林

并查集森林就是一种将每个集合以树表示的数据结构，其中每个节点保存保存着他的父节点的引用（换句话说，就是每个节点指向他的父节点）。

节点表示方式

int par[size];
//数组的下表表示元素（元素的编号），值表示父亲（父亲的编号）。

在并查集森林中，每个集合的代表即是集合的根节点。

“查找”：根据其父节点的引用，递归地进行查找，直到到底树根。然后再一层一层的返回。

“联合”：将两棵树合并到一起，这通过将一棵树的根连接到另一棵树的根，来实现。

1.2. 操作

1.2.1.MakeSet初始化操作

将每个元素初始化为一个单元素集合。

代码

int par[size];
void makeSet(){
    //size是元素的数量，按具体情况来定
    for(int i = 0;i < size;i++)
        par[i] = i; 
}

效果图

1.2.2.find确定元素所属集合操作

传入一个元素，从而得到该元素所在集合的代表

确定元素所属集合的代码

int find(int x){
    if(par[x] == x)
        return x;
    else 
        return Find(par[x);
}

有了这个操作我们就得到了代表。因此，我们可以通过该操作判断两个元素是否属于同一集合。

判断两个元素是否属于同一集合的代码

bool same(int x, int y){
    int rootx = find(x);
    int rooty = find(y);
    return rootx == rooty;
}

1.2.3. union合并两个集合操作

获取这两个集合的代表，然后一个集合的代表指向另一个集合的代表，这样这两个集合就能合并了。

合并两个集合的代码

void union(int x, int y){
    int rootx = find(x);
    int rooty = find(y);
    par[rootx] = rooty;
}

1.3. 并查集的优化

1.3.1. 路径压缩

刚才我们说过，寻找祖先时采用递归，但是一旦元素一多起来，或退化成一条链，每次find都将会使用O(n)的复杂度，这显然不是我们想要的。以下是一个退化的例子。

退化成链地场景

①以下两个集合合并

②然后又来了一个元素4，需要合并

③…

为此，我们可以使用“路径压缩”。路径压缩是一种在执行“查找”时扁平化树结构的方法。关键在于在路径上的每个节点都可以直接连接到根上；他们都有同样的表示方法。为了达到这样的效果，Find递归地经过树，改变每一个节点的引用到根节点。得到的树将更加扁平，为以后直接或者间接引用节点的操作加速。

Tao：简单地说， 路径压缩，就是在查找根操作时，依次将该路径上的子孙指向根。

具体代码如下。

find操作（路径压缩版）

int find(int x){
    if(par[x] == x)
        return par[x];
    else 
        return par[x] = find(par[x]);
}

一种更简便的写法

int find(int x){
    return par[x] == x?par[x]:(par[x] = find(par[x]));
}

1.3.2. 按秩合并

在合并时，总是将更小的树连接至更大的树上。因为影响运行时间的是树的深度，更小的树添加到更深的树的根上将不会增加秩，除非它们的秩相同。在这个算法中，术语“秩”替代了“深度”，因为同时应用了路径压缩时秩将不会与高度相同。单元素的树的秩定义为0，当两棵秩同为r的树联合时，合并后的秩为r+1。只使用这个方法将使最坏的运行时间提高至每个MakeSet、Union或Find操作为O(logn) 。

int rank[size];
void init(){
    for(int i = 0;i , size;i++)
        rank[i] = 0;
}

void union(int x, int y){
    int rootx = find(x);
    int rooty = find(y);
    if(rank[rootx] < rank[rooty])
        par[rootx] = rooty;
    else if(rank[rootx] > rank[rooty])
        par[rooty] = rootx;
    else {
        par[rootx] = rooty;
        rank[rooty]++;
    }
}

1.4. 时间复杂度和空间复杂度

这两种方法的优势互补，同时使用二者的程序每个操作的平均时间仅为O(α（n）)， α（n）是n = f(x) = A（x,x）的反函数，其中A是急速增加的阿克曼函数。 因为α(n)是其的反函数，故α(n)在n十分巨大时还是小于5。因此，**平均运行时间时一个极小的常数 **。

1.5. 应用

洛谷P1551）亲戚

题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
题目描述
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
输入格式
第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。
以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。
接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
输出格式
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

​ 这其实是一个很有现实意义的问题。我们可以建立模型，把所有人划分到若干个不相交的集合中，每个集合里的人彼此是亲戚。为了判断两个人是否为亲戚，只需看它们是否属于同一个集合即可。因此，这里就可以考虑用并查集进行维护了。

参考

• https://zhuanlan.zhihu.com/p/93647900
• *并查集

两篇参考都讲得很不错，可以看一下