Tarjan 算法族：SCC、割点、桥的统一框架
内容提要
Tarjan算法通过一次DFS和low数组求强连通分量、割点与桥。关键区别：SCC的low仅由栈内顶点更新；无向图按边编号跳过父边；桥判定为low[v]>disc[u]，割点为low[v]≥disc[u]，根节点需单独统计子树。文章还对比了Kosaraju算法、递归与迭代实现，指出链式图存在递归深度风险，并给出对拍实验与工程建议。
延伸解读
有向与无向：low 数组的两套不变量
文章强调，Tarjan 算法族中 low 数组的定义在有向图和无向图中并不相同。有向图求 SCC 时，low 只能由仍在栈中的顶点更新，否则会把不同 SCC 错误合并；无向图求割点/桥时，low 需按边编号跳过父边，但允许平行边作为回边。这种差异源于问题本质：SCC 关注顶点间的互相可达，而割点/桥关注删除后连通性的变化。理解这两套不变量是正确实现的关键。
重边场景：按边编号跳过父边
文章用最小反例说明，在无向多重图中，若简单地用顶点编号跳过父节点，会忽略第二条平行边，导致误判桥。正确做法是按边编号跳过进入当前顶点的那条无向边，这样平行边仍可作为回边更新 low 值。这一细节在竞赛代码中常被忽略，但却是保证算法正确性的必要条件。
递归深度风险与迭代实现
文章指出，递归实现的 DFS 在链式图上深度可达顶点数，可能引发栈溢出。实验显示，200000 个顶点的链式图递归深度为 200000，而系统栈限制通常为 8 MiB。因此，生产环境如 LLVM 和 NetworkX 都采用迭代版本，用显式栈模拟递归，避免系统调用栈的限制。迭代版需要保存当前顶点、下一条待扫边和父顶点等信息。
工程选择：输出顺序与图存储
文章提醒，Tarjan 算法输出的 SCC 顺序是缩点 DAG 的逆拓扑序，但具体顺序依赖邻接表遍历顺序。若后续阶段需要确定性输出，应按顶点编号或组件最小顶点重新排序。此外，图存储结构影响迭代帧的设计：使用 vector<vector<int>> 时保存边迭代器，而 CSR 或连续边数组则保存边下标。这些工程细节不影响算法正确性，但影响代码的健壮性和性能。
Q&A
Tarjan算法中，求强连通分量时low数组的更新规则是什么？为什么只能由栈内顶点更新？
有向图SCC的low[u]定义为从u出发经树边再接至多一条指向仍在SCC栈中顶点的边能到达的最小disc值。更新规则为：low[u] = min(disc[u], min(low[v] for tree edges), min(disc[v] for edges to v on stack))。关键限制是边必须指向仍在栈中的顶点。若指向已弹出的SCC，说明对方已封闭，不能回到当前子树，用它更新low会将两个不同SCC错误合并。
Tarjan算法中割点和桥的判定条件有什么区别？为什么一个是>=一个是>？
桥判定：low[v] > disc[u]；割点判定（非根）：low[v] >= disc[u]。区别在于：桥删除的是边(u,v)，只要v的子树能通过回边回到u本身（low[v] == disc[u]），这条边就不是唯一通道，所以需要严格大于；割点删除的是顶点u，回到u本身没有用，必须能到达u的祖先，所以low[v] >= disc[u]即可。根节点是割点当且仅当它有至少两个DFS树子节点。
在无向图中处理重边时，为什么不能简单地用if (v == parent) continue来跳过父边？正确做法是什么？
因为无向图的重边（平行边）中，除了进入当前顶点的树边外，另一条平行边是合法的回边，应该用来更新low值。如果简单跳过所有指向父节点的边，会丢失这条回边，导致将树边误判为桥。正确做法是按边编号跳过进入当前顶点的那条无向边（即parent_edge），而不是按顶点跳过。如果使用成对存储的有向弧，可以跳过反向弧编号id ^ 1。
Tarjan SCC和Kosaraju算法在实现和性能上有什么主要区别？
Tarjan SCC只需一次DFS，不需要构造转置图，使用SCC栈、on_stack和low数组；Kosaraju需要两次DFS，需要构造转置图，使用完成序列。在边访问次数上，对30000个随机小图，Tarjan递归版和迭代版都访问469223条边，Kosaraju访问938446条边，正好是两遍遍历。但实际时间还受邻接表布局、缓存和语言运行时影响，不能简单说Tarjan快一倍。
为什么生产环境中的Tarjan算法通常采用迭代实现而不是递归？迭代实现的关键是什么？
因为递归DFS在链式图上递归深度等于顶点数，容易导致栈溢出。例如200000个顶点的链，递归深度可达200000层，而系统栈通常只有8MB。迭代实现用显式栈模拟DFS，将系统调用栈换成可控的堆上数组。关键是用帧结构保存当前顶点、下一条待扫边和父顶点等信息，遍历未访问边时压入新帧，处理完所有邻边后弹帧并回传low值。
Tarjan算法输出的强连通分量顺序有什么特点？工程中如何处理输出顺序？
Tarjan SCC输出的是缩点DAG的逆拓扑序：若分量A有边到分量B，通常先弹出B。Kosaraju第二遍的发现顺序也依赖第一遍完成序。如果后续阶段需要确定性输出，应按顶点编号或组件最小顶点再排序，不要把当前邻接表顺序当作接口承诺。
