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

How does dynamic programming helps to solve this problem. Tutorials say run dp on every node of trie and determine state for each node. My question is how to use that data to determine final solution. I understand, we can get who would win by looking at the state of each leaf of trie. But what i do for more than one leaf. Also what first refers to here, person who started first game or person who starts each game ?

Problem: https://mirror.codeforces.com/contest/456/problem/D Tutorial: https://mirror.codeforces.com/blog/entry/13336