题解

思路

若两个顶点互相可达，它们属于同一个强连通分量。直接求所有点对之间的可达关系可以解决较小规模；在完整范围内，需要在线性时间内识别深度优先搜索树中能够回到祖先的点集。

做法

从每个尚未访问的顶点开始深度优先搜索。记录顶点第一次被访问的时间戳，以及从该顶点的搜索子树出发、经过至多一条指向栈内顶点的边能够到达的最小时间戳。

搜索到一条树边时，先递归处理终点，再用终点的最小时间戳更新当前顶点。搜索到指向栈内顶点的边时，用该顶点的访问时间戳更新当前顶点。

如果某个顶点的最小时间戳等于它的访问时间戳，那么它是一个强连通分量在搜索树中的根。不断弹出栈顶直到弹出该顶点，得到一个完整的强连通分量。

为满足输出顺序，先为每个分量内的顶点排序，再按分量中最小顶点的编号对全部分量排序。

正确性证明

搜索栈恰好保存已经访问但所属强连通分量尚未确定的顶点。对栈内顶点 $u$，最小时间戳记录了从 $u$ 的搜索子树能够到达的最早栈内祖先。

当某个顶点 $u$ 的最小时间戳等于其访问时间戳时，$u$ 的搜索子树中仍在栈内的顶点无法到达 $u$ 之前的栈内顶点；另一方面，这些顶点都由 $u$ 沿搜索树可达，并能沿搜索边或回边回到 $u$。因此，从栈顶到 $u$ 的所有顶点两两可达，构成一个完整强连通分量，且不会遗漏或混入其他分量。

每个顶点恰好入栈、出栈一次，所以算法最终得到且仅得到图中的全部强连通分量。最后的排序只改变输出顺序，不改变分量划分。

复杂度

• 时间复杂度：$O(n+m)$，另有分量内与分量间排序的 $O(n\log n)$。
• 空间复杂度：$O(n+m)$。