并查集
入门
并查集（union-find set）是一种不算太“低级”的数据结构，在算法竞赛中比较常见。简而言之，它专门用来高效地处理不相交集合（disjoint sets）的合并及查询问题。
Bernard A. Galler和Michael J. Fischer于1964年提出了并查集的森林表示形式：用一棵（多叉）树来表示一个集合，树中的每个节点都保存着对它的父节点的引用，所有的不相交集合即可形成一个森林，并且每个集合的“代表”就是对应的树的根节点。
根据上述表示形式，我们就可以定义并查集的三种基本操作。下面用伪码表示之。
-
从单节点x创建集合
每个集合刚开始都只有一个元素，通过后面的合并操作再形成多元素的集合。
function make(x) {
x.parent = x;
}
-
查询x位于哪个集合
注意返回的是x所在集合的根节点，前面说过，根节点可以作为集合的“代表”。
function find(x) {
if (x.parent == x) {
return x;
} else {
return find(x.parent);
}
}
当然也可以写成迭代形式。
function find(x) {
while (x.parent != x) {
x = x.parent;
}
return x;
}
-
合并x、y所在的两个集合
就是分别找到它们所处集合的根节点，并将两个集合的根连接在一起。
function union(x, y) {
rootx = find(x);
rooty = find(y);
if (rootx == rooty) {
return;
}
rootx.parent = rooty;
}
上面的写法是最朴素的逻辑，虽然简单，但性能有风险——因为集合形成的树有可能会非常不平衡，甚至成为单枝树（退化成线性的）。所以在实际应用时会采取两方面优化：一是路径压缩（path compression），二是按秩合并（union by rank）。
路径压缩
根据并查集结构的定义，树的每个节点其实都可以直接连接到根节点，而树表示的集合是不变的。那么我们在执行查询操作时，可以顺便对查询路径中经过的每个节点都递归地更改指向，让它们连接到根节点上，使得树尽量扁平化，之后再执行查询操作遍历的节点就会变少，效率提高。最理想情况下，树应该只有两层，顶层只有根节点，第二层是所有叶子节点。
下面给出路径压缩思路下查询操作的逻辑。
function find(x) {
if (x.parent != x) {
x.parent = find(x.parent);
}
return x.parent;
}
以及等价的迭代写法，即先将父节点指向祖父节点，再将当前节点指向父节点。
function find(x) {
while (x.parent != x) {
x.parent = x.parent.parent;
x = x.parent;
}
return x;
}
按秩合并
我们已经知道，树的深度会影响并查集算法的效率，那么在两个集合合并时，可以人为地将深度较小的树连接到深度较大的树的根节点上。合并的结果树的深度要么不会增加，要么只增加1（即当两棵树的深度相同时）。这里引入“秩”（rank）的概念：
- 单元素集合树的秩为0；
- 当两个秩同为r的集合树做合并操作时，结果树的秩为r + 1。
实际实现时，可以将秩存储在根节点。为什么不直接沿用深度的概念呢？因为按秩合并几乎都与路径压缩一同使用，路径压缩之后树会变扁平，深度和秩就不是一回事了。
下面给出按秩合并思路下创建集合和合并操作的逻辑。
function make(x) {
x.parent = x;
x.rank = 0;
}
function union(x, y) {
rootx = find(x);
rooty = find(y);
if (rootx == rooty) {
return;
}
if (rootx.rank < rooty.rank) {
rootx.parent = rooty;
} else if (rootx.rank > rooty.rank) {
rooty.parent = rootx;
} else {
rooty.parent = rootx;
rootx.rank++;
}
}
复杂度
如果同时使用上述两种优化，如果在有n个元素的并查集上进行m次查询和合并操作，其时间复杂度为O(mα(n))，其中α(n)为阿克曼函数A(n, n)的反函数。证明过程非常硬核，详见《算法导论》第21章第4节。
英文维基中《Proof of O(log*n) time complexity of union–find》一文也给出了平摊时间复杂度为O(mlog*n)的证明，相对容易明白一些。其中log*为迭代对数，即：
不管是反阿克曼函数还是迭代对数，它们的增长速度都极其缓慢，接近常数级别，这也从侧面说明了并查集的高效性。
应用举例
并查集常常用来解决网络中的连通性问题。这里的网络是广义的，除了计算机网络之外，还可以是社交体系里的人际关系网、生物学里的食物网等等。如果将网络抽象为图结构，那么并查集可以方便地确定两点是否连通（是否在同一个集合内），以及共有多少个连通分量（不相交集合数）。下面举个简单的例子。
LeetCode 547：Friend Circles
题目大意：一个班级有N（N≤200）位学生，给出一个N*N的矩阵M，M[i][j]=M[j][i]=1表示第i位和第j位学生是朋友关系。确定这些学生中有多少个“朋友圈”，“朋友圈”指的是一组有直接或间接朋友关系的人。
这就是上述“在人际关系网中确定连通分量数”的例子，朋友圈的数量其实就是并查集内不相交集合的数量。它的数据规模比较小，就算是用朴素解法也可以AC，但是作为例题，我们还是老老实实写一个完全版，代码如下。
class Solution {
final int MAXN = 201;
int[] parent = new int[MAXN];
int[] rank = new int[MAXN];
void make(int x) {
parent[x] = x;
rank[x] = 0;
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx != ry) {
if (rank[rx] <= rank[ry]) {
parent[rx] = ry;
rank[ry] = Math.max(rank[rx] + 1, rank[ry]);
} else {
parent[ry] = rx;
rank[rx] = Math.max(rank[rx], rank[ry] + 1);
}
return true;
}
return false;
}
public int findCircleNum(int[][] M) {
int n = M.length, result = n;
for (int i = 0; i < n; i++) {
make(i);
}
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (M[i][j] == 1) {
if (union(i, j)) {
result--;
}
}
}
}
return result;
}
}
在实际应用中，并查集用简单的数组就能表示：parent数组存储某节点的父节点，rank数组存储（根）节点的秩。另外，为了避免合并完之后再重新扫描统计一遍根节点的数量，可以在每一次成功的合并之后将总数减去1（初始的朋友圈数量自然是N）。
如果题目改成判断两个人x、y是否位于同一个朋友圈内，使用条件find(x) == find(y)即可。
根据本节开头对连通性问题的描述，这道题（以及其他不少可以用并查集解决的题目）用DFS解决也比较自然，解法就略去了。不过，并查集无法获知两点之间的路径，而DFS可以，所以要根据实际情况灵活使用。
Kruskal算法与并查集
算法介绍
Kruskal算法是图的两种经典最小生成树（MST）算法之一（另外一个是Prim），在大学数据结构和图论课程中肯定会讲到。这里先简介一下它的算法流程：
- 新建图G'，其中包含原图G中相同的顶点，但没有边；
- 将原图G中所有的边按照权值从小到大排序；
- 从权值最小的边开始，如果这条边连接的两个顶点在G'里不存在于同一个连通分量中（即这条边是桥边，添加它不会构成环），则将它添加到G'；
- 重复上一步，直到G'中的所有顶点都位于同一个连通分量，即形成最小生成树。
为了方便理解，下面的图示出在一张图上执行Kruskal算法的流程。绿色边是最小生成树的边，红色边是不满足上述步骤3条件的边。
由Kruskal算法的流程可见，关键点有二：一是需要判断两个点是否位于同一个连通分量，二是合并两个连通分量（添加桥边之后），这恰好是并查集所擅长的。
该算法的时间复杂度可以这样考虑：第1步初始化为O(|V|)，第2步的排序为O(|E|log|E|)（很多排序算法都是这个复杂度），而第3步并查集操作的复杂度是O(|E|α(|V|))。由于这几步是顺序执行的，整个算法的时间复杂度应该取上面三个的最大者，即O(|E|log|E|)。
下面还是举个例题来说明。
应用举例
LeetCode上好像没几个MST的题目，从当年整天刷的POJ挑一个简单的吧。
POJ 1251：Jungle Roads
纯粹的MST题目，输入各个村庄之间道路的长度，求能够将这些村庄全部连接起来的最小路径总长。
根据题意，图的顶点数小于27，边数小于75，规模也很小，所以Kruskal+路径压缩并查集就可以水过去了。代码如下。
const int MAXN = 101;
int n, m, cnt, w;
char u[4], v[4];
int parent[MAXN];
struct Edge {
int u, v, w;
}e[MAXN];
bool comp(Edge a, Edge b) {
return a.w < b.w;
}
int find(int x) {
return x == parent[x] ? x : parent[x] = find(parent[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
parent[x] = y;
}
int kruskal(int n) {
int result = 0;
for (int i = 0; i < n; i++) {
if (find(e[i].u) != find(e[i].v)) {
unite(e[i].u, e[i].v);
result += e[i].w;
}
}
return result;
}
int main() {
while (scanf("%d", &n) && n) {
cnt = 0;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
for (int i = 0; i < n - 1; i++) {
scanf("%s%d", u, &m);
for (int j = 0; j < m; j++) {
scanf("%s%d", v, &w);
e[cnt++] = {u[0] - 'A', v[0] - 'A', w};
}
}
sort(e, e + cnt, comp);
printf("%d\n", kruskal(cnt));
}
return 0;
}
成功AC，民那晚安。
