sharmahappy654's blog

By sharmahappy654, history, 4 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

| Write comment?