并查集!

并查集最擅长做的事情——将两个元素合并到同一集合、判断两个元素是否在同一集合中。

并查集用到了树的父结点表示法。在并查集中，每个元素都保存自己的父亲结点的编号，如果自己就是根

结点，那么父亲结点就是自己。这样就可以用树形结构把在同一集合的点连接到一起了。

(1) 并查集的实现

struct node

{

int parent;      // 表示父亲结点。当编号i==parent时为根结点。  int count;       // 当且仅当为根结点时有意义：表示自己及子树元素的个数  int value;       // 结点的值

} set[N];

int Find(int x)       // 查找算法的递归版本（建议不用这个）

{

return (set[x].parent==x) ? x : (set[x].parent = Find(set[x].parent));

}

int Find(int x)        // 查找算法的非递归版本

{  int y=x;  while (set[y].parent != y)   // 寻找父亲结点   y = set[y].parent;    while (x!=y)       // 路径压缩，即把途中经过的结点的父亲全部改成y。 {   int temp = set[x].parent;   set[x].parent = y;   x = temp; } return y; } void Union(int x, int y)    // 小写的union是关键字。 { x=Find(x); y=Find(y);    // 寻找各自的根结点  if (x==y) return;     // 如果不在同一个集合，合并    if (set[x].count > set[y].count) // 启发式合并，使树的高度尽量小一些 {   set[y].parent = x;   set[x].count += set[y].count; } else {   set[x].parent = y;   set[y].count += set[x].count; } } void Init(int cnt)      // 初始化并查集，cnt是元素个数 {  for (int i=1; i<=cnt; i++) {   set.parent=i;   set.count=1;   set.value=0; } } void compress(int cnt)     // 合并结束，再进行一次路径压缩 {  for (int i=1; i<=cnt; i++) Find(i); }

说明： Ÿ 使用之前调用Init()！ Ÿ Union(x,y)：把 x 和 y 进行启发式合并，即让节点数比较多的那棵树作为“树根”，以降低层次。

Ÿ Find(x)：寻找 x 所在树的根结点。Find的时候，顺便进行了路径压缩。

上面的Find有两个版本，一个是递归的，另一个是非递归的。

Ÿ 判断 x 和 y 是否在同一集合：if (Find(x)==Find(y)) ……

Ÿ 在所有的合并操作结束后，应该执行compress()。

Ÿ 并查集的效率很高，执行 m 次查找的时间约为O(5m)。