并查集算法，英文是 Union-Find，是解决动态连通性（Dynamic Conectivity）问题的一种算法。动态连通性是计算机图论中的一种数据结构，动态维护图结构中相连信息。简单的说就是，图中各个节点之间是否相连、如何将两个节点连接，连接后还剩多少个连通分量。
动态连通性其实可以抽象成给一幅图连线。假设用一个数组表示一堆节点，每个节点都是一个连通分量。初始化视图如下：
Figure 1. 并查集初始化
并查集的一个重要操作是 union(a, b)，就是将节点 a 和节点 b 建立连接。如图所示：
Figure 2. 并查集合并
union(a, b) 还可以将已经建立的两个“子网”进行连接：
Figure 3. 并查集再合并
|
Tip
|
在合并时，是修改根节点的指针 parent[ap] = bp，而不是修改节点的指针 parent[a] = bp。
|
并查集除了 union，还有一个重要操作是 connnected(a, b)。判断方法也很简单，从节点 a 和 b 开始，向上查找，直到两个节点的根节点，判断两个根节点是否相等即可判断两个节点是否已经连接。为了加快这个判断速度，可以对其进行“路径压缩”，直白点说，就是将所有树的节点，都直接指向根节点，这样只需要一步即可到达根节点。路径压缩如图所示：
Figure 4. 并查集路径压缩
简单代码实现如下：
link:{labdir}/UnionFind.java[role=include]