algorithm - 使图表有根

Question

问题的定义:如果图中的每个节点 u 都存在从 v 到 u 的有向路径，则节点 v 将被称为“根”。

给定一个有向图 G=，其中没有任何“根”。

我需要找到一种算法来决定我们是否可以添加一条边，以便在结果图中有一个“根”。

有什么想法吗？

Answer 1

为您的图计算强连通分量 (SCC) 图。如果该 SCC 图恰好有两个源 A 和 B，添加从 A 中的任何节点到 B 中的任何节点的有向边将导致 A 中的每个节点成为最终图中的“根”节点。

源是没有传入边的节点。

您可以使用 Tarjan's SCC algorithm 在 O(|V| + |E|) 时间内计算 SCC 图.所以整体复杂度为 O(|V| + |E|)。