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 set — 1).