Disjoint Set Data Structure recursive find_parent gets wrong answer

general
, , ,
1

I was trying to solve “Almost Union Find problem” from Kattis. I used disjoint set to solve this problem. My problem is, I got wrong answer when I used the following recursive find_parent function in my code -

int find_p(int x){
 if(par[x]!=x)
   par[x] = find_p(par[x]);

 return par[x];
}

But, the following find_parent function gets AC.

int find_p(int x){
int root = x;

while(par[root]!=root)
root = par[root];

int cn = x;

while(cn!=root)
{
int curp = par[cn];
par[cn] = root;
cn = curp;
}

return root;
}

Don’t they do the same thing?

Here’s my complete code,

AC Code

2

They should behave identically. Are you sure there are no other differences between the correct and incorrect code?