并查集

并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

这个是维基百科上的定义，建议看看维基百科，说明得非常易懂。

下面简单说一下我的理解。

先说一下可能的应用场景：

• 遍历连通块。比如：(A,B)表示A地点和B地点可达。那当我们已知(A,B)、(C,D)、(B,C)时，可以推出(A,D)、(A,C)、(B,D）。换句话说，(A,B,C,D)是一个连通块。

就连通块这个例子，对并查集的说明如下：
并查集，本质上就是若干棵树，同一棵数内的节点存在某种关系（连通块里的可达）。也可以把一棵树看做一个集合（连通块）。每棵树会有一个根节点，根节点的父节点指向自己。

那么在构建并查集的过程中，会涉及到将两个树合并（因为发现A树的节点a跟B树的节点b同样存在关系），合并的方法是：

function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

可以看到，合并的方法里有一个查找方法Find，它的伪代码如下：

function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)

可以看出，是一个递归查找，直到找出所在树的根节点。

wiki里提到一个优化方案：“路径压缩”：将树扁平化，即同一棵树内，除根节点外的所有节点的父节点都指向根节点。所以Find可以改成：

function Find(x)
     if x.parent != x
        x.parent := Find(x.parent)
     return x.parent

顺便把树给拍平。