我们如何选择哪个元素在 Union-find 数据结构中具有代表性？

Question

当我们合并两个集合时，例如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？如果我们希望它更改为另一个代表怎么办？

Answer 1

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

时反转你的参数

Answer 2

合并集合的代表，将是排名最高的那个。有关详细信息，这是一个很好的 read.

我们如何选择哪个元素在 Union-find 数据结构中具有代表性？

How can we choose which element to be representative in a Union-find data structure?

algorithm

set

data-structures

union-find