我有个问题，但我想不出解决办法。事情是这样的：
我有一个有向图，有N个节点和M个链接，没有循环我需要找出链的最小数目，这样每个节点只属于一个链。
例子：
7 11 7个节点；11个链路
12个
15个
2 3个
25个
27个
3到4／/链路存在于3和4之间
36个
46个
5 4个
56个
73个
答案是：2
一个例子是
链条：2-7-3-6
链条：1-5-4
谢谢。
最佳答案
他不需要知道这个图是否是哈密顿量，知道它是一个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
关于algorithm - 链数最少的有向图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2284404/