sharmahappy654's blog

By sharmahappy654, history, 2 years ago, In English

Problem link: https://codeforces.com/contest/217/problem/A
Submission link: https://codeforces.com/contest/217/submission/78364143

I am trying to use Union and find to count disjoint sets but getting WA on testcase 45. I know this problem can be solved with dfs too but I don't want to use that.

Can somebody explain what's wrong in my code or is my implementation Union and find wrong ?

I am storing given coordinates in a vector of pairs and checking each pair against other if they lie on the same line vertically or horizontally.

If so, I am calling union on them.

Finally I am storing representative of each group in a set to count total number of disjoint sets. And since we need to output the minimum number of points needed to make graph connected, i am outputting (size of — 1).

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not sure why it is so, but instead of doing ss.insert(sa[i]), go for ss.insert(find(i)), i.e. add root to set instead of parent. It might happen that in few test cases, path compression isn't completed yet and so adding parent won't give the correct answer. You must add the root and check distinct roots for connected components.