并查集兩種優化方法（按秩合并，壓縮存儲）

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;
}