Как мы можем выбрать, какой элемент должен быть репрезентативным в структуре данных поиска на основе Union?

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.