why swap function is use in union find algorithm? How rank or size array is used for optimization

cs.stackexchange https://cs.stackexchange.com/questions/124971

  •  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

Was it helpful?

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
scroll top