algorithm - 未连接的有向图顶点的最大子集的大小？

Question

给定一个有向图，我怎样才能找到顶点的最大子集的大小，使得它们中的任何一个都没有通过有向路径连接？

这个问题（或解决它的算法）有一个通用名称吗？

（提示： “根据 Dilworth 定理，这个问题实际上相当于计算传递闭包后 DAG 上覆盖的最小链数。因此，这个问题可以简化为二分图上的最大匹配。”）

Answer 1

不知道名字，估计是Disjoint-set数据结构的子问题

使用 Union Find，您可以确定所有连通图。

最初，每个节点都在其组中。检查每个节点并将其所有直接子节点添加到节点的组根中。这是基本的联合查找。

然后，最大子集由每个组的一个顶点组成。

在最坏的情况下，当每个节点都连接到所有其他节点时，这应该花费 O(n²)，因为每个节点都被检查 n 次。