由于有向图，我怎么能找到verticies使得没有两个人是通过向路径连接？的最大子集的大小

Given a directed graph, how can I find the size of a maximal subset of verticies such that no two of them are connected by a directed path?

请问这个问题（或者说解决它的算法）有一个共同的名字？

Does this problem (or the algorithm that solves it) have a common name?

（提示：根据迪尔沃思的定理，这个问题其实就相当于一个DAG以链的最小数量的覆盖计算的传递结束后。因此，这个问题是可以减少的最大对手关于二分图。）

(Hint: "According to Dilworth's theorem, this problem is actually equivalent to the minimum number of chains cover on a DAG after calculate the transitive closure. Thus, this problem can be reduce to maximum match on bipartite graph.")

推荐答案

我不知道这个名字，我想这是对的不相交集数据结构

I don't know about the name, I guess it's a sub problem of the Disjoint-set data structure

使用联盟查找，您可以确定所有的连通图。

Using Union Find, you can determine all the connected graph.

最初，每个节点是它的基团。检查每个节点，并添加所有的直接子女节点的组root。这是基本的联盟查找。

Initially, each node is on its group. Check every node and add all its direct children to the node's group root. This is basic Union Find.

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

The largest subset is then composed by one vertice from each group.

在最坏的情况下，其中，当每一个节点连接到所有其他节点，这应为O（N²），为每一个节点已选中n次

In worst case, which when every node is connected to all other nodes, this should take O(n²) as every node is checked n time.