Problem link: https://codeforces.net/contest/217/problem/A
Submission link: https://codeforces.net/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).
You were skipping the path compression step which is very crucial that's why your implementation was failing the testcases.
Here's Your corrected code with slight modification.
Submission Link
Hope it helps.
Happy Coding!