图算法：Tarjan 算法求强连通分量

什么是强连通分量 (SCC)？

在有向图中，如果两个顶点 u 和 v 能相互到达（即存在从 u 到 v 的路径，也存在从 v 到 u 的路径），则称这两个顶点是强连通的。强连通是顶点之间的一种等价关系。有向图中的极大强连通子图，被称为强连通分量 (Strongly Connected Components, SCC)。

Tarjan 算法的核心思想

Tarjan 算法是一个基于深度优先搜索 (DFS) 的算法，它能在 O(V+E) 的时间内找出有向图中的所有强连通分量。

算法为每个节点 u 维护两个关键的变量：

• dfn[u]: 深度优先搜索中 u 被访问到的时间戳（顺序编号）。
• low[u]: u 节点（以及其 DFS 树中的子树）能够通过 最多一条非树边（返祖边或横叉边）追溯到的、在栈中最早的节点的 dfn 值。

算法还使用一个栈来保存当前正在访问的路径上的节点。

算法步骤

1. 初始化 dfn 和 low 数组，以及一���空栈 s。
2. 从任意未访问过的节点开始进行 DFS 遍历。
3. 对于当前访问的节点 u： a. 设置 dfn[u] = low[u] = ++timestamp。 b. 将 u 压入栈 s 中，并标记为在栈中。 c. 遍历 u 的每一个邻居 v： i. 如果 v 未被访问过，则递归调用 tarjan(v)，然后用 v 的 low 值更新 u 的 low 值：low[u] = min(low[u], low[v])。 ii. 如果 v 已经被访问过 且在栈中，说明找到了一条返祖边，用 v 的 dfn 值更新 u 的 low 值：low[u] = min(low[u], dfn[v])。
4. 当 DFS 从 u 回溯前，检查是否有 dfn[u] == low[u]。
   • 如果成立，说明 u 是它所在强连通分量的“根”。
   • 此时，从栈顶不断弹出元素，直到 u 被弹出。所有这些被弹出的节点共同构成一个强连通分量。

伪代码

function tarjan(u):
  dfn[u] = low[u] = ++timestamp
  stack.push(u)
  in_stack[u] = true

  for each edge (u, v):
    if v is not visited:
      tarjan(v)
      low[u] = min(low[u], low[v])
    else if v is in_stack:
      low[u] = min(low[u], dfn[v])

  if dfn[u] == low[u]:
    // u is the root of an SCC
    create a new SCC
    while true:
      v = stack.pop()
      in_stack[v] = false
      add v to current SCC
      if u == v:
        break

Tarjan 算法是图论中一个非常优美且高效的算法，常用于缩点等操作，是解决复杂图问题的基础。