强连通分量
使用 Tarjan 将相互可达的节点分组
强连通分量 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
什么是 SCC
强连通分量是一个极大的节点集合，其中每个节点都可以沿有向边到达其他每个节点。
我们为何关心它
将每个 SCC 合并为一个超级节点，就能把任意有向图转换为DAG。这样就更容易分析相互依赖关系。
Tarjan算法一遍完成
Tarjan算法只需一次 DFS 就能找到所有 SCC。它的运行时间为 O(V + E)，与一次普通遍历的开销相同。
发现编号
按照 DFS 第一次访问节点的顺序，为每个节点分配一个发现时间。这些编号可以帮助您比较哪个节点更早被访问。
disc = [-1] * n
timer = 0低链接值
每个节点的低链接值是从该节点可达的最小发现编号，其中也包括经过反向边到达的节点。它确定了该分量的边界。
low = [-1] * n将节点压入栈
当 DFS 进入一个节点时，设置它的 disc 和 low，然后将它push到一个栈中。这个栈保存可能属于同一分量的节点。
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = True根据子节点更新 Low
递归进入未访问的子节点后，将它的 low 值向上合并：low[u]变为自身与子节点 low 值中的最小值。
dfs(v)
low[u] = min(low[u], low[v])处理反向边
如果某个邻居已经在栈中，它就是该 SCC 中的祖先。请使用它的 disc 来降低 low[u]。
elif on_stack[v]:
low[u] = min(low[u], disc[v])找到分量根节点
当low[u] 等于 disc[u]时，节点 u 就是一个 SCC 的根节点。栈中位于它上方的所有节点都属于同一个分量。
弹出分量
到达根节点后，不断从栈中pop节点，直到移除 u。弹出的这一组节点恰好构成一个强连通分量。
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: break另一种选择：Kosaraju算法
更喜欢分两遍处理吗？Kosaraju算法先运行 DFS，反转每条边，然后按照完成顺序再次运行 DFS，以逐个提取 SCC。
快速检查
在 Tarjan算法的 DFS 期间，节点 u 满足 low[u] == disc[u]。这说明了什么？
回顾：使用 Tarjan算法求 SCC
在一次 DFS 中跟踪 disc 和 low，将活动节点保存在栈中，并在low 等于 disc时弹出一个分量。时间复杂度为 O(V+E)。🧩
常见问题解答
「强连通分量」课时是免费的吗？
是的 — 「强连通分量」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「强连通分量」这节课中我会学到什么？
使用 Tarjan 将相互可达的节点分组 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「强连通分量」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。