-3

I am stuck on this problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1099

Currently, I have sets, where each element in the set are friends. However, I don't know how to proceed with the enemies. Could anyone point me in the right direction?

WilliamHarvey
  • 49
  • 5
  • It appears that "enemies" is equivalent to "not friends". Also, there are only two sets of friends, though there can be many sets of *known* friends. Is that enough to go by? – Beta Aug 10 '21 at 17:26
  • 2
    A question should be self-contained. Although a link can be helpful, the essential information to understand the question should be embedded here. Secondly, you should show your efforts, preferably with your code. Give example input for which your code goes wrong, or else, where you are stuck. – trincot Aug 10 '21 at 17:34
  • The site is currently down.. – devoured elysium Aug 11 '21 at 01:21

1 Answers1

0

This problem requires a modification to the normal disjoint set data structure.

You can determine whether two people are friends or enemies if they are connected by any sequence of two-person relations. If X and Y are connected like X-f-A-f-B-e-C-e-D-f-Y, for example, then you know that X and Y are friends.

You can use a disjoint set data structure to keep track of this connectivity -- Create a set for each person, and merge two disjoint sets whenever a member of one is related to a member of the other.

In addition, for each person that is not a set leader, you should remember whether he is a friend or enemy of his parent. In this way you can walk from any two people up to their set roots and determine how they are related.

This extra information is easily maintained during union-by-size/rank and path compression.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87