并查集两种优化方法（按秩合并，压缩存储）

1）按秩合并。

     按秩合并的基本思想是使包含较少结点的树德根指向包含较多结点的树的根，而这个树的大小可以抽象为树的高度，即高度小的树合并到高度大的树，这样资源利用更加合理。

     为了实现一个按秩合并的不想交集合森林，要记录下秩的变化。对于每个结点x，有一个整数rank[x]，它是x的高度（从x到其某一个后代叶结点的最长路径上边的数目）的一个上界。（即树高）。当由MAKE-SET创建了一个单元集时，对应的树中结点的初始秩为0，每个FIND-SET操作不改变任何秩。当对两棵树应用UNION时，有两种情况，具体取决于根是否有相等的秩。当两个秩不相等时，我们使具有高秩的根成为具有较低秩的根的父结点，但秩本身保持不变。当两个秩相同时，任选一个根作为父结点，并增加其秩的值路径压缩。

简单代码解释：

void Union(int a, int b)
 {   
       if(village[a].weight == village[b].weight) {//树高一样   
       village[b].parent = a;    
       village[a].weight += 1;   
       } 
       else if (village[a].weight > village[b].weight) {//矮树并入高树   
       village[b].parent = a;//并入a 
       } 
       else {        village[a].parent = b;//并入b    
       }
}
           

2）路径压缩

     是在FIND-SET操作中，把查找路径上的每个结点都直接指向根结点。路径压缩并不改变结点的秩。关于路径压缩，看图理解，之间为FIND-SET操作前集合，之后为FIND-SET操作后集合。此时，查找路径上的每一个结点都直接指向根。

路径压缩代码实现方式有两种：递归式和非递归式。

1）递归方式

伪代码：

FIND-SET(x) 1  if x ≠ p[x] 2     then p[x] ← FIND-SET(p[x]) 3  return p[x]

     这个过程FIND-SET是一种两趟方法（two-pass method）：一趟是沿查找路径上升，直至找到根；第二趟是沿查找路径下降，以便更新每个结点，使之直接指向根。对FIND-SET（x）的每一次调用，都会在第3行返回p[x]。如果x为根，则不执行第2行，返回p[x] = x。这种情况下递归结束。否则，执行第2行，且参数为p[x]的递归调用返回一个指向根的指针。第2行更新结点x，使之直接指向根，并在第3行返回这个指针。

int Find(int x) 
{   
      if(root[x] == -1)  
      {        return x;    }
      return root[x] = Find(root[x]);
}
           

2）非递归方式

//非递归版路径压缩
int Find (int n) {//r->root   
       int r = n;    
       while (r != root[r]) {//寻找根结点        
       r = root[r];  
       }    
        int x = n, y;    
        while (x != r) {//压缩路径，全部赋值为根结点的值        
         y = root[x];      
         root[x] = r;     
         x = y;    
       }   
     return r;
}