我有一组节点和它们之间的一组有向边。边缘没有重量。
如何找到必须添加的最小数量的边以使图强连接（即应该有一条从每个节点到所有其他节点的路径）？这个问题有名字吗？
这是一个非常经典的图问题。
- 运行类似 Tarjan-SCC 算法的算法来查找所有 SCC。考虑
每个SCC作为一个新的顶点，在这些顶点之间链接一条边新的
顶点根据原图，我们可以得到一个新的图。
显然，新图是有向无环图（DAG）。
- 在DAG中，找到所有入度为0的顶点，我们定义它们
{X};找到所有出度为0的顶点，我们定义
我的}。
- 如果 DAG 只有一个顶点，则答案为 0；否则，答案
是最大值（|X|，|Y|）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
