algorithm - 如何检查图中的所有节点是否可以从所有其他节点访问？

Question

我正在尝试解决这个问题：

有 n 个城市和 m 个航班连接。您的任务是检查您是否可以使用可用航班从任何城市前往任何其他城市。

输入

第一个输入行有两个整数 n 和 m：城市数和航班数。城市编号为 1,2,…,n。

在此之后，有 m 行描述航班。每行有两个整数 a 和 b：有一个从城市 a 到城市 b 的航班。所有航班均为单程航班。

我的方法是在每个节点上做一个 dfs，跟踪我们访问过的所有节点。然后检查我们是否访问了所有节点。不过，这在 n^2 中运行。不过这超时了。

有人可以指导我通过更优化的算法吗？

标签： algorithmgraph

Answer 1

您的每个节点都可以从其他每个节点到达的标准等同于测试图中强连通分量的数量是否为 1。

有一些众所周知的高效算法可以找到图的强连通分量，例如Kosaraju 的算法和Tarjan 的强连通分量算法，它们都在具有n 个节点和m个边的图上运行 O( n + m ) 时间。