如何解决这个 Union-Find 不相交集问题? [英] How to solve this Union-Find disjoint set 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?

推荐答案

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

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

您可以确定两个人是朋友还是敌人，如果他们通过任何两人关系序列相连.例如，如果 X 和 Y 像 X-f-A-f-B-e-C-e-D-f-Y 那样连接，那么您就知道 X 和 Y 是朋友.

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.

这篇关于如何解决这个 Union-Find 不相交集问题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！