Tarjan 算法复盘：一次递归里塞下三件事
发布 修订 分类 coding
当前浏览器未执行 JavaScript，下面是本篇的 Markdown 原文，内容一字未改。
Tarjan 的优雅之处在于它的「一鱼三吃」：同一次 DFS，同一对数组，三种图论结论一起出来。
<!-- more -->
## 两个数组的含义
- `dfn[u]`：DFS 序，第一次访问 u 的编号。
- `low[u]`：从 u 出发，通过**树边和后向边**能回溯到的最小 dfn。
更新规则：设 v 是 u 的孩子，边 `(u, v)` 是树边时用 `low[v]` 更新；是后向边（v 已在栈里或未结束）时用 `dfn[v]` 更新。
## 桥与割点
- 若 `low[v] > dfn[u]`，则边 `(u, v)` 是**桥**。
- 若 `low[v] >= dfn[u]` 且 u 不是根，则 u 是**割点**；u 是根时，需要有两棵以上子树才是割点。
```cpp
void dfs(int u, int in_edge) {
dfn[u] = low[u] = ++idx;
int child = 0;
for (int e = head[u]; e; e = nxt[e]) {
int v = to[e];
if (e == (in_edge ^ 1)) continue; // 不走反向边，但有重边时仍可走
if (!dfn[v]) {
dfs(v, e); low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) is_bridge[e] = is_bridge[e ^ 1] = true;
if (low[v] >= dfn[u] && in_edge) is_cut[u] = true;
++child;
} else low[u] = min(low[u], dfn[v]);
}
if (!in_edge && child > 1) is_cut[u] = true; // 根的特殊处理
}
```
用成对存边（`e ^ 1` 是反向边）比记录父节点更稳，因为能正确处理重边：两条平行边里总有一条不是反向边，于是 `low` 会被正确压低，桥不会被误判。
## 强连通分量
改成带栈的版本：进入时压栈，回溯完若 `low[u] == dfn[u]` 就不断弹栈直到 u，得到一个 SCC。缩点之后，图变成 DAG，就可以接拓扑排序与 DP 了。
| 目标 | 判断条件 | 附加结构 |
| --- | --- | --- |
| 桥 | `low[v] > dfn[u]` | 无 |
| 割点 | `low[v] >= dfn[u]`，根需两棵子树 | 无 |
| 边双连通分量 | 删掉所有桥 | 无 |
| 强连通分量 | `low[u] == dfn[u]` | 栈 + `ins[]` 标记 |
## 手算验证的习惯
写完 Tarjan 我一定会用下面这张小图手算一遍：$1-2$、$2-3$、$3-1$、$3-4$。预期：$\{1,2,3\}$ 是一个 SCC，$3-4$ 是桥，$3$ 是割点。如果代码跑出来的结果和手算不一致，八成是 `low` 的更新用错了 `dfn` 还是 `low`。
> [!WARN]
> 又一个常见错：把「已访问」当成「已出栈」。SCC 里必须用 `in_stack` 判断，不能用 `dfn` 是否存在，否则跨分量会误连。
## 复杂度与实现细节
时间 $O(n + m)$，空间 $O(n)$。递归深度可能到 $n$，$n > 2 \times 10^5$ 时考虑栈溢出，可以手写栈或调大系统栈。
