链数最小的有向图
链数最小的有向图
提问于 2010-02-17 21:06:47
我有问题，但我想不出解决办法。事情是这样的：
我有一个有向图，它有N个节点和M个链接，没有圈。我需要找出链的最小数目，这样每个节点都只属于一个链。
示例：
7 11 7节点；11链路
1 2
1 5
2 3
2 5
2 7
3 // 3和4之间存在联系
3 6
4 6
5 4
5 6
7 3
答案是:2
一个例子是
链: 2-7-3-6
链: 1-5-4
谢谢。
回答 1
Stack Overflow用户
回答已采纳
发布于 2010-02-17 22:13:47
他不需要知道这个图是否是哈密顿的-知道它是一个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
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2284404
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号