algorithm - How to solve this Union-Find disjoint set problem?

Question

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?

Answer 1

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.