algorithm - 具有最少链数的有向图

Question

我有一个问题，但我想不出解决办法。它是这样的:

我有一个有向图，有 N 个节点和 M 个链接，没有循环。我需要找出最小链数，以便每个节点只属于一个链。

例子:

7 11 7 nodes; 11 links
1 2
1 5
2 3
2 5
2 7
3 4 // link exists between 3 and 4
3 6
4 6
5 4
5 6
7 3

答案是:2

一个例子是
链条:2-7-3-6
链:1-5-4

谢谢。

Answer 1

他不需要知道该图是否是哈密尔顿图 - 知道它是一个 DAG 就足够了。大概是比赛或者在线评委的问题吧？作业看起来确实太难了。

此处的解决方案:http://www2.cs.science.cmu.ac.th/person/rogaway/ps3-solns.pdf

要有效地找到匹配项，请考虑 Hopcroft Karp 算法:http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm