本文的主要内容如下：

• 并查集的简单介绍
• 并查集模板代码
• 保证性能的两个启发式策略：路径压缩和按秩合并
• 时间复杂度介绍
• Ackermann(4,1)到底有多大

---

何谓并查集

并查集，在《算法导论》中的术语是“用于不相交集合的数据结构”。比较抽象，笔者觉得还不如“并查集”来的好理解。

先举个简单的例子来直观感受一下“并查集”解决的问题：

假设有编号分别为0,1,2,3,4,5的6个人，

告诉你0和4是一伙儿的，2和3同属一伙，3和5同属一伙，请问一共有几个团伙？

这个问题可以靠简单推理得出答案。但是如果人数比较多，团伙关系复杂的话，就需要借助算法工具来解决。

并查集就是解决这类集合（或者图）的连通性问题，一个很好用的工具。

接下来，用数组来表达这个例子：

数组arr[0..5]记录这6个人，他们各自的“状态”，即他们各自属于哪个团伙。

一开始，令arr[i] = i (i=0..5)，每个人都属于不同的团伙，也可以说是都各自独立。

接着，既然0和4一伙，那么让arr[4] = 0。即两个人一伙的话，可以规定编号大的要“听从”编号小的，4的上级是0。

同理，arr[3] = 2, arr[5] = 3。

那么，如此一来数组就变成了：[0,1,2,2,0,3]

其中有3个联通分支（团伙）：

以0为首的分支：0<–4 (0的上级是0，4的上级是0)

以1为首的分支：1 （1的上级是1）

以2为首的分支：2<–3<–5 （2的上级是2，3的上级是2，5的上级是3）

模板代码

// 开启了路径压缩和按秩合并的并查集
public class UnionFind {
    int[] parent;
    int[] size;
    // 当前连通分支数目
    int branchCount;

    public UnionFind(int n) {
        this.branchCount = n;
        this.parent = new int[n];
        this.size = new int[n];
        Arrays.fill(size, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        // 路径压缩
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }

    public boolean unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        // 按秩合并
        if (size[x] < size[y]) {
            int temp = x;
            x = y;
            y = temp;
        }
        parent[y] = x;
        size[x] += size[y];
        --branchCount;
        return true;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int branchCount() {
        return branchCount;
    }
}

路径压缩和按秩合并

并查集本身理解起来不困难，关键是要理解保证性能的两个启发式策略：路径压缩和按秩合并。

1、路径压缩
路径压缩(union by rank)还是很好实现的。
在finx(x)查找元素x所属分支根元素的过程中，将向上查找路径上的所有元素的parent直接指向最终找到的根。实现上，这是通过递归一层一层调用，最终一层一层返回并进行赋值来做到的。
那么，下一次查找这条路径上的任意一个元素，可以直接一步定位到根，即缩短了查找路径。

2、按秩合并
按秩合并(path compression)实现稍微麻烦一点，需要一个额外的size[]数组，size[i]记录以i为根的分支内节点的数量。
有了size[]数组，在合并的时候，将节点数量少的分支，向节点数量多的分支进行合并。

时间复杂度

使用路径压缩和按秩合并的情况下，作用于n个元素上的m个不相交集合，
建立起整个联通关系的时间复杂度为O(m·α(n))，其中α(n)<=4。

//α(n)的值（摘自《算法导论》）
0 (n=0,1,2)
1 (n=3)
2 (n=4,5,6,7)
3 (8<= n <=2047)
4 (2048<= n <= X)，其中X是阿克曼函数值Ackermann(4,1)，是一个远远比10^80大的数。

所以，对于不是大到特别特别离谱的n来说，α(n)<=4是没毛病的。

后记

如果想要知道Ackermann(4,1)到底是多大的一个数，可以查看：很大、大得离谱的数

---