具有最小链数的有向图

Question

3

我有一个问题，但我无法找到解决方案。它是这样的：

我有一个有向图，其中有N个节点和M条链接，且没有循环。我需要找出最少的链的数量，以便每个节点仅属于一个链。

例如：

7 11 7个节点；11条链接 1 2 1 5 2 3 2 5 2 7 3 4 // 3和4之间存在链接 3 6 4 6 5 4 5 6 7 3

答案是：2

例如：链：2-7-3-6 链：1-5-4

谢谢。

- user273386

1

"无循环"..."我需要找出最小的循环次数"? 你是指链，对吗？" - Mark Byers

抱歉，我会修改。 - user273386

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

他不需要知道这个图是否是哈密顿图——只要知道它是一个DAG就足够了。这可能是一个比赛或在线评判的问题吧？看起来太难以至于不像是家庭作业。