vsanjay_nitdgp's blog

UVA — 10158 — DSU
By vsanjay_nitdgp, history, 9 years ago, In English

PROBLEM LINK: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1099

could you please say the idea fo this problem in DISJOINT SET UNION.

Thank you.

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is the only time of the year where you can see downvotes on Legendary Grandmaster post asking for help :))

The problem title is self-explanatory: You should use some twist on Disjoint set data structure.

When I was solving this problem I got away with adding one additional datafield to disjoint set — for each set I had one more number showing the enemy of that set.

Then you need to think carefully what do you do with enemy of set when two sets are combined. Start with idea that Enemy of your Enemy is your Friend and if two sets with two enemies are united, then you need to unite both friends and both enemies.

→ Reply