Codeforces functionality may be limited from June 18, 19:00 (UTC) to June 19, 3:00 AM (UTC) due to technical maintenance. Polygon will work as usual. ×

sharmahappy654's blog

By sharmahappy654, history, 4 years ago, In English

Problem link:
Submission link:

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?
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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!