问题的定义：一个节点v将被称为“根”iff对于图中的每个节点u有一个从v到u的有向路径。
给定一个无“根”的有向图g。
我需要找到一个算法，来决定我们是否可以添加一条边，以便在结果图中有一个“根”。
有什么想法吗？
最佳答案
计算图的强连接组件（SCC）图。如果该scc图正好有两个源a和b，则将a中任意节点的有向边添加到b中任意节点将导致a中的每个节点成为最终图中的“根”节点。
源是没有传入边的节点。
您可以使用Tarjan's SCC algorithm在O（| V |+| E |）时间内计算SCC图总体复杂度为O（Ⅴ+＋e）。