在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构——并查集来描述。
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint
Sets）的合并及查询问题。常常在使用中以森林来表示。进行快速规整。
并查集的主要操作：1 合并两个不相交集合 (并)2 判断两个元素是否属于同一个集合(查)
合并操作很简单：先设置一个数组Father[x]，表示x的“父亲”的编号。那么，合并两个不相交集合的方法就是，找到其中一个集合最父亲的父亲（也就是最久远的祖先），将另外一个集合的最久远的祖先的父亲指向它。
查的操作比较简单，可以使用递归操作来查找节点的根节点
优化：
（1）find_set(x)时 ，路径压缩
刚才我们说过，寻找祖先时采用递归，但是一旦元素一多起来，或退化成一条链，每次查找父节点都将会使用O（n）的复杂度，这显然不是我们想要的。
对此，我们必须要进行路径压缩，即我们找到最久远的祖先时“顺便”把它的子孙直接连接到它上面。这就是路径压缩了。使用路径压缩的代码如下，时间复杂度基本可以认为是常数的。 如图：
（2）union(a, b) 时，按秩合并
即合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小。
实现代码：
int father[MAX]; /* father[x]表示x的父节点*/
int rank[MAX]; /*rank[x]表示x的秩*/
void Make_Set(int x)
{
father[x] = x; //根据实际情况指定的父节点可变化
rank[x] = 0; //根据实际情况初始化秩也有所变化
}
/* 查找x元素所在的集合,回溯时压缩路径*/
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]); //这个回溯时的压缩路径是精华
}
return father[x];
}
/*
按秩合并x,y所在的集合
下面的那个if else结构不是绝对的，具体根据情况变化
但是，宗旨是不变的即，按秩合并，实时更新秩。
*/
void Union(int x, int y)
{
x = Find_Set(x);
y = Find_Set(y);
if (x == y) return;
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
}
时间复杂度：
O(n*α(n))
其中α(x),对于x=宇宙中原子数之和,α(x)不大于4
事实上，路经压缩后的并查集的复杂度是一个很小的常数。
hdoj 上有一些题可以练习：http://acm.hdu.edu.cn/problemclass.php?id=721