217A Ice Skating

Revision en1, by sharmahappy654, 2020-04-28 13:56:52

Problem link: https://mirror.codeforces.com/contest/217/problem/A
Submission link: https://mirror.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 set — 1).

Tags #union-find

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English sharmahappy654 2020-04-28 13:57:55 4 Tiny change: ' (size of set — 1).' -> ' (size of - 1).'
en1 English sharmahappy654 2020-04-28 13:56:52 834 Initial revision (published)