我正在尝试自学图论，现在尝试了解如何在图中找到SCC。我已经阅读了关于 SO 的几个不同的问题/答案（例如，1、2、3、4、5、6、7、8），但我找不到一个可以遵循的完整分步示例。
根据CORMEN (Introduction to Algorithms)，一种方法是：
- 调用 DFS(G) 计算每个顶点 u 的完成时间 f[u]
- 计算转置(G)
- 调用 DFS(Transpose(G))，但在 DFS 的主循环中，按 f[u] 递减的顺序考虑顶点（如步骤 1 中计算的）
- 将步骤 3 的深度优先森林中每棵树的顶点输出为单独的强连通分量
观察下图（问题是来自这里的 3.4。我在这里和这里找到了几个解决方案，但我试图自己分解并理解它。）
第 1 步：调用 DFS(G) 计算每个顶点 u 的完成时间 f[u]
从顶点 A 开始运行 DFS：
请注意格式为 [Pre-Vist, Post-Visit] 的 RED 文本
第 2 步：计算转置 (G)
步骤 3. 调用 DFS(Transpose(G))，但在 DFS 的主循环中，按 f[u] 递减的顺序考虑顶点（如步骤 1 中计算的）
好的，所以顶点按访问后（完成时间）值递减的顺序排列：
{E、B、A、H、G、I、C、D、F、J}
所以在这一步，我们在 G^T 上运行 DFS，但从上面列表中的每个顶点开始：
- DFS(E)：{E}
- DFS(B)：{B}
- DFS(A)：{A}
- DFS(H): {H, I, G}
- DFS(G)：从列表中删除，因为它已经被访问过
- DFS(I)：从列表中删除，因为它已经被访问过
- DFS(C): {C, J, F, D}
- DFS(J)：从列表中删除，因为它已经被访问过
- DFS(F)：从列表中删除，因为它已经被访问过
- DFS(D)：从列表中删除，因为它已经被访问过
步骤4：将步骤3的深度优先森林中每棵树的顶点输出为单独的强连通分量。
所以我们有五个强连通分量：{E}, {B}, {A}, {H, I, G}, {C, J, F, D}