不相交集数据结构

问题描述：

这是在$ C $下findind相交集合

this is the code for findind disjoint sets

    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 ??? NMA初学者遗憾而且什么是发现一步做？

why are we incrementing rank if ranks are eqaul???n m a beginner sorry and also what is the find step doing??

答

由于在这种情况下 - 你添加一个树是一种子树其他的 - 这使得原有的子树增加它的大小

Because in this case - you add one tree is a "sub tree" of the other - which makes the original subtree increase its size.

看一看下面的例子：

1           3
|           |
2           4

在上文中，每个树的等级为2。
现在，让我们说1将是新的统一的根，你会得到下面的树：

In the above, the "rank" of each tree is 2.
Now, let's say 1 is going to be the new unified root, you will get the following tree:

在加盟后的1的等级是3， rank_old（1）+ 1 - 如预期

不相交集数据结构

相关推荐