why swap function is use in union find algorithm? How rank or size array is used for optimization
-
29-09-2020 - |
Question
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (size[a] < size[b])
swap(a, b);
parent[b] = a;
size[a] += size[b];
}
}
Q1.why we need this swapping? can't we do like this without swapping
if (size[a] < size[b])
parent[a] = b;
size[b] += size[a];
Q2.what is the difference between size array and rank array.Is Rank means the height of a node and size means no of node in that tree which contains this node
Solution
To answer your first question, it is a matter of style. If you do it your way, then the code appears twice. Code duplication is more prone to bugs, since you have to duplicate every change that you make, taking care (in this case) to switch $a$ and $b$.
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange