不相交集數據結構

Question

這是findind不相交的代碼設置

class disjoint_sets { 
     struct disjoint_set { 
     size_t parent; 
     unsigned rank; 
     disjoint_set(size_t i) : parent(i), rank(0) { } 
     }; 
     std::vector<disjoint_set> forest; 
     public: 
     disjoint_sets(size_t n){ 
     forest.reserve(n); 
     for (size_t i=0; i<n; i++) 
     forest.push_back(disjoint_set(i)); 
     } 
     size_t find(size_t i){ 
     if (forest[i].parent == i) 
     return i; 
     else { 
     forest[i].parent = find(forest[i].parent); 
     return forest[i].parent; 
      } 
      } 
     void merge(size_t i, size_t j) { 
      size_t root_i = find(i); 
     size_t root_j = find(j); 
      if (root_i != root_j) { 
      if (forest[root_i].rank < forest[root_j].rank) 
      forest[root_i].parent = root_j; 
      else if (forest[root_i].rank > forest[root_j].rank) 
      forest[root_j].parent = root_i; 
      else { 
      forest[root_i].parent = root_j; 
      forest[root_j].rank += 1; 
       } 
      } 
      } 
      }; 

爲什麼我們增加排名，如果排名是eqaul ??? n×m個初學者對不起 ，也什麼是查找一步做？

Answer 1

因爲在這種情況下 - 您添加一棵樹是另一棵樹的「子樹」 - 這會使原始子樹增加其大小。

看一看下面的例子：

1   3 
|   | 
2   4 

在上面，每個樹的「排名」是2
現在，讓我們說1將是新的統一的根，你將得到下面的樹：

1 
/\ 
/ \ 
3  2 
| 
4 

聯接的「1」的排名後3，rank_old(1) + 1 - 如預期。