并查集是一种树型的数据结构，用于处理一些不交集（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
顺便把树给拍平。
