algorithm - 如何解决这个联合查找不相交集问题？

Question

我被困在这个问题上： https ://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1099

目前，我有集合，集合中的每个元素都是朋友。但是，我不知道如何对付敌人。谁能指出我正确的方向？

Answer 1

这个问题需要对正常的不相交集数据结构进行修改。

如果两个人通过任何两个人关系的序列连接，您就可以确定他们是朋友还是敌人。例如，如果 X 和 Y 像 XfAfBeCeDfY 一样连接，那么您知道 X 和 Y 是朋友。

您可以使用不相交集数据结构来跟踪这种连通性——为每个人创建一个集合，并在其中一个成员与另一个成员相关时合并两个不相交集。

此外，对于每个不是固定领导者的人，你应该记住他是父母的朋友还是敌人。通过这种方式，您可以从任何两个人走到他们的根，并确定他们是如何相关的。

在按大小/等级和路径压缩联合期间，可以轻松维护这些额外信息。