Disjoint set union find algorithm problem

#1

Suppose we have 2 disjoint sets
1<->2<->3
4<->5.
And suppose par[1] = par[2] = par[3] = 3 and par[4] = par[5] = 5.
When we find union(2,4)
par[2] = 5 , no of disjoint sets become 1
and again we do union(3,5) , no disjoint sets according to video code will become 0 as par[3] = 3 != par[5] = 5

#2

@chikugoel1998
when it will do union(3,5) it will first find superparent of 3 and 5.
so here superparent(3) = 3, superparent(5)=5;
now, it will make par[3] = 5, here 3 and 5 are the one which are found by finding the superparent of a and b which are passed to union(a,b).

Ya when after union(2,4) it will do union(3,5) then no benefit as it is already connected.

#3 
int getSuperPar(int x){
        if(par[x] == x){
            return x;
        }
        return par[x] = getSuperPar(x);
    }

When we will get super parent of 3 the above function would return 3 or not?

#4

After doing union(2,4), superparent(3) will return 5.
As you can see in union function, when we do union for 2,4 then we actually joining them after finding their superparent.

1 Like
#5

oh yes got it, how foolish of me :man_facepalming:

#6

It’s fine.
Please Mark this doubt as resolved.