并查集

并查集，就是Union-Find Set，也称不相交集合 (Disjoint Set)。这在数据结构中本是很简单的一种东西。当然，我是指算法的实现简单，而非其理论分析简单。但我今天还是要扯一下这个，因为我突然发现我这几天写的并查集都是错的，今天做题时才发现。所以还是把这个很简单的数据结构总结一下。

正如它的名字揭示的，并查集的基本操作有两个：Union和Find。其中Find(x)返回元素x所在的集合的编号，Union(i,j)将i与j所在的集合合并，也就是说在此之后对它们中的每一个调用Find的返回值必须是一样的。

实现时采用父亲表示法的树结构，保证所有在一个集合里的元素都在一棵树内，集合的代表元素就是根。初始时所有节点的父节点都是自身，查找时只须沿着向上的路径查找即可；如果要将两棵树合并只须将其中一棵的根的父节点设为另一棵树的根即可。最主要的优化是所谓路径压缩。简言之，就是在Find的实现时并不简单的return find(U[x]); 而是 return U[x]=find(U[x]); 这样就将当前节点到根的路径上的所有节点的父亲都设为了根，将原本可能比较长的路径“压缩”了。当然这是递归的实现，非递归的话需要沿路径走两次，第一次找到根，第二次再改变。

union操作更简单，只是U[find(x)]=find(y);一句而已。我前两天写Tarjan算法时把这一句错写成U[x]=find(y)，竟然也AC了……汗……不过今天做另一道需要并查集的题目就没那么幸运了。

路径压缩的并查集n个操作的序列的均摊复杂度为O(nα(n))，其中 α是阿柯曼函数的一个反函数，增长极慢，在可以想象的n的范围内不超过5，故可视为常数。

并查集的一般用途就是用来维护某种具有自反、对称、传递性质的关系的等价类。

实现并查集只需要一个数组和两个分别是两行和一行的函数，故不再发示例代码了。