Disjoint set union

help
1

i have just started learning dsu … someone plz help me … i am stuck in the hackerearth beginner problem … ???
https://www.hackerearth.com/submission/40329165/
why it is giving WA ? i am unable to find corner cases ?? why is there a need to take a size array and initialising parent of each node as -1 initially as most of the submissions are… plz help me why i am getting WA??

2

this is the whole playlist where i have taught this data structure in detail with example problems

2 Likes
3

yes brother … i have seen this playlist only …and i have also posted a comment in your video on teachers dilemma problem on dsu

4

The problem is it’s hard to reach every comment for me , sorry for that man.
let’s see where you are going wrong.
time to check your code (hope this is well formatted)

5

no problem brother … i am really very thankful to you for making a great playlist and helping everybody …

6

the problem is in this for loop

for(i=1;i<=n;i++)
    {mp[par[i]]++;
    }

it is not necessarily true that par[i] actually represents parent of ith node (since it is possible that path compression has not been applied to i or after that par has changed in union function)

so just change it to

  for(i=1;i<=n;i++)
        {mp[find(par[i])]++;
        }

and everything will work fine.
good luck

2 Likes
7

or simply

for(i=1;i<=n;i++)
        {mp[find(i)]++;
        }
1 Like
8

ok …got it …thanks a lot brother for helping me…
you are doing great and awesome work by making such great videos …(concepts along with example problems) … keep on helping us …thanks once again

1 Like
9

you’re welcome man , good luck for further learning.