题目与使用场景
图有 n 个顶点和 m 条有向边，顶点可能没有出边，边可能重复，输入不保证连通。强连通分量是顶点集合，其中任意两个顶点都能互相到达。实现需要返回分量列表，并说明如何通过缩点得到有向无环图。
面试官考察什么
- 是否能正确维护 DFS 索引、
low值、栈和在栈标记。 - 能否解释树边、返祖边和指向已完成分量边对
low更新的差异。 - 是否覆盖非连通图、自环、重边和递归深度风险。
- 是否能给出 O(n+m) 时间与 O(n) 辅助空间，并说明测试不变量。
作答前的澄清问题
先确认顶点编号是否连续、是否允许重复边、输出分量内部是否需要排序，以及运行环境是否限制递归深度。再确认图规模、是否需要在线增量更新、是否只需判断两个顶点是否同分量。若图规模很大，我会说明递归版本与显式栈版本的取舍。
30 秒回答框架
我会做一次 DFS，并为每个顶点分配递增索引和当前可回溯到的最小索引 low。顶点入栈并标记在栈后，遍历邻居：未访问邻居先递归并用它的 low 更新当前值；仍在栈中的邻居用其索引更新。若 low 等于自身索引，当前顶点是分量根，从栈顶弹到它为止。每条边和顶点只被常数次处理，因此复杂度是 O(n+m)。
分步骤深入解答
- 初始化状态。 为每个顶点准备索引、
low、在栈标记和组件编号；索引从 0 或 1 单调递增。对所有未访问顶点启动 DFS，覆盖非连通图。 - 处理未访问邻居。 递归访问邻居后执行
low[u] = min(low[u], low[v])。这条更新代表通过 DFS 子树能回到更早的栈顶。 - 处理栈内邻居。 若邻居仍在栈中，用邻居的索引更新
low[u]。已经弹出并归属其他分量的邻居不能参与回溯，否则会把两个分量错误合并。 - 识别根并弹栈。 当
low[u]等于index[u]时，u 是当前分量根。持续弹栈并清除标记，直到弹出 u；被弹出的顶点共同组成一个强连通分量。 - 处理边界。 自环会让顶点保持为单点分量；重边只会重复执行同一最小值更新；孤立顶点在入栈后立即成为单点分量。
- 验证和缩点。 检查每个顶点恰好属于一个分量，并验证组件间边构成 DAG。随机小图可用传递闭包或 Kosaraju 结果对照，大图再验证复杂度与栈深度。
高质量示范回答
我会维护四个数组：递增的 index、回溯值 low、在栈标记和组件编号。DFS 进入顶点时分配 index 并入栈。遇到未访问邻居，递归结束后用邻居的 low 更新当前顶点；遇到仍在栈中的邻居，只用邻居的 index 更新。已经完成的分量不会参与更新。
当 low[u] == index[u]，u 是根，我从栈顶弹出直到 u，得到一个分量并清除标记。对所有未访问顶点启动 DFS，所以不要求图连通。每个顶点入栈和出栈一次，每条边检查一次，时间 O(n+m)，辅助空间 O(n)。测试会覆盖自环、重边、孤立点、长链、多个环和非连通图，并检查分量划分和缩点 DAG。
常见错误
- 对所有已访问邻居都用其 low 更新，导致跨已完成分量错误回溯。
- 弹出分量后忘记清除在栈标记，使后续边把旧顶点当作当前路径。
- 只从一个起点 DFS，漏掉非连通图中的分量。
- 把
low等于当前 index 误解为没有边，而忽略它表示当前顶点是分量根。 - 递归深度超过语言栈限制却没有说明显式栈、分块输入或运行时配置方案。
追问及应对
为什么已经弹出的顶点不能更新 low？
它已经属于一个完成的分量，不再是当前 DFS 路径上的可回溯祖先。使用它的 low 会跨越分量边界，破坏分量极大性。
如何证明每个分量只弹出一次？
每个顶点入栈一次，只有根条件成立时才从栈顶弹出；弹出后在栈标记被清除，后续 DFS 不会再次入栈。因此每个顶点恰好归属一个分量。
Tarjan 与 Kosaraju 如何选择？
Tarjan 一次 DFS、无需转置图，适合希望降低遍历和存储的实现；Kosaraju 用两次 DFS，概念直观且容易拆成独立阶段。两者都能达到 O(n+m)，选择应依据语言栈限制、代码可读性和现有图表示。