0

当我们合并两个集合时，例如 A={1,2,3} 和 B={6,7,8}，让 1,8 分别代表这两个集合，现在如果我们合并两个集合会是什么结果集的代表？我们可以根据我们的选择来选择吗？在我下面的代码中

#include<iostream>
#define MAX 10001
int rank[MAX];int parent[MAX];
void swap(int x,int y)
{
int temp=0;
temp=x;
x=y;
y=temp;
 }
void make_set (int v) {
parent[v] = v;
rank[v] = 0;
 }

 int find_set (int v) {
 if (v == parent[v])
    return v;
 return parent[v] = find_set (parent[v]);
 }

  void union_sets (int a, int b) {
 a = find_set (a);
 b = find_set (b);
 if (a != b) {
    if (rank[a] < rank[b])
        swap (a, b);
    parent[b] = a;
    if (rank[a] == rank[b])
        ++rank[a];
   }
      }
  int main()
  {
    for(int i=1;i<=3;i++)
  {
  make_set(i);
    }
   std::cout<<find_set(1)<<"\n";
   union_sets(1,2);
   union_sets(2,3);
   std::cout<<find_set(2)<<"\n"; 
 return 0;
  }

我得到的答案是 1？如果我们希望它更改为另一个代表怎么办？

4

2 回答 2

1

您的 DSU 实现很好，因为您使用 rank 数组来合并两个集合，请记住，合并是由于每个集合的排名而完成的，以使合并的集合平衡。
但是如果要加入两个具有相同等级的集合，则加入将根据您的 union_sets 函数参数的顺序。
所以回答你的问题：如果你想从 1 改变（这只有在目标集具有相同等级时才有可能）你所要做的就是在调用 union_sets 时反转你的参数。

于 2017-01-22T11:07:08.427 回答
0

合并集的代表将是排名最高的代表。有关更多信息，这是一个很好的阅读。

于 2017-01-22T11:10:09.457 回答