给定一个有向图，我怎样才能找到顶点的最大子集的大小，使得它们中的任何一个都没有通过有向路径连接？
这个问题（或解决它的算法）有一个通用名称吗？
（提示： “根据 Dilworth 定理，这个问题实际上相当于计算传递闭包后 DAG 上覆盖的最小链数。因此，这个问题可以简化为二分图上的最大匹配。”）
问问题
270 次
1 回答
0
不知道名字，估计是Disjoint-set数据结构的子问题
使用 Union Find，您可以确定所有连通图。
最初，每个节点都在其组中。检查每个节点并将其所有直接子节点添加到节点的组根中。这是基本的联合查找。
然后，最大子集由每个组的一个顶点组成。
在最坏的情况下，当每个节点都连接到所有其他节点时，这应该花费 O(n²)，因为每个节点都被检查 n 次。
于 2012-10-19T10:29:19.200 回答