有向图中可到达所有顶点的顶点识别及O(n+m)时间可行性探讨

可以做到，核心思路是利用**强连通分量（SCC）**和缩点后的有向无环图（DAG）特性，全程保持线性时间复杂度。具体步骤如下：

1. 提取所有强连通分量 #

使用Kosaraju算法、Tarjan算法或Gabow算法，这三种算法都能在O(n+m)时间内找出图中所有SCC。同一SCC内的顶点互相可达，因此分量内的顶点要么全部满足“能到达所有其他顶点”的条件，要么全部不满足。

2. 构建缩点DAG #

将每个SCC视为一个超级节点，若原图中存在从SCC X到SCC Y（X≠Y）的边，则在DAG中添加一条X指向Y的边（注意去重，避免重复边）。这一步的时间复杂度仍是O(n+m)。

3. 定位并验证候选分量 #

在缩点后的DAG中，只有满足以下条件的分量才可能包含目标顶点：

• 首先检查入度为0的分量数量：如果DAG中有多个入度为0的分量，那么不存在任何顶点能到达所有其他顶点——因为这些入度为0的分量之间无法互相到达，没有顶点能同时覆盖它们。
• 如果只有一个入度为0的分量，将其作为候选分量。接下来对这个候选分量在DAG中执行一次DFS或BFS，验证它是否能到达所有其他超级节点。这一步的时间复杂度是O(n'+m')（n'为分量数，m'为缩点后边数），仍属于O(n+m)范畴。

4. 确定最终结果 #

如果候选分量能到达DAG中所有其他超级节点，那么该分量中的所有原顶点就是满足条件的顶点；否则，图中不存在这样的顶点。

复杂度说明 #

所有步骤的时间复杂度均为线性O(n+m)，远优于朴素的O(n(n+m))方法。

内容的提问来源于stack exchange，提问作者Daniel