Блог пользователя vsanjay_nitdgp

Автор vsanjay_nitdgp, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.