В операции объединения, которая лучше на основе ранга или размера, где операция поиска выполняется с использованием сжатия пути
Согласно моему пониманию, объединение по размеру лучше, потому что сжатие пути в операции поиска также изменяет ранг, который не обновляется, тогда как размер остается тем же. Но в некоторых редакционных статьях для задач было выполнено объединение по рангу. Я не понимаю основного различия между ними.
Наборы A и B должны быть объединены
Инициализируется с размером [i]=1 и Arr[i]=i для всех i до n
void union_sizebased(int Arr[ ],int size[ ],int A,int B)
{
int root_A = root(A);
int root_B = root(B);
if(size[root_A] < size[root_B ])
{
Arr[ root_A ] = Arr[root_B];
size[root_B] += size[root_A];
}
else
{
Arr[ root_B ] = Arr[root_A];
size[root_A] += size[root_B];
}
}
Инициализируется с Arr[i]=i и rank[i]=0 для всех i до n
void union_rankbased(int Arr[ ],int rank[ ],int A,int B)
{
int root_A = root(A);
int root_B = root(B);
if(rank[root_A] < rank[root_B ])
{
Arr[ root_A ] = Arr[root_B];
}
else if(rank[root_B] < rank[root_A ]
{
Arr[ root_B ] = Arr[root_A];
}
else
{
Arr[root_B]=Arr[root_A]; // Arbitrarly choosing between two and assigning
rank[root_A]++;
}
}