连通性算法 · low-link 三题

把一遍 DFS 走过的痕迹记下来，每个点只留两个整数：dfn 是它第几个被访问，low 是它的子树顺着至多一条非树边能回到的最小 dfn。这一对数字构成 low-link 内核，Tarjan 在 1972 年的同一篇论文里用它同时给出了 strongly connected component 与 articulation point 两个线性算法。

本系列的三页依次是：SCC 与 condensation；articulation point、bridge 与 biconnected component；以及把 2-SAT 归约成 SCC 判定。第三页完全建立在第一页之上——two-sat/core 里没有第二份 Tarjan，它直接调用 scc.ts 的 tarjanSteps。

判据只差一个等号： 无向图里 low[v] >= dfn[u] 说明 u 是 articulation point，low[v] > dfn[u] 说明边 u–v 是 bridge。差别在于「子树能否回到 u 自己」——回到 u 则删掉 u 仍会断，回不到 u 才连这条边都不能少。 顺序也是产出的一部分： Tarjan 弹出 SCC 的先后恰是 condensation 的逆拓扑序，于是 2-SAT 取值不必再跑一遍拓扑排序，比较两个分量编号即可。 SCC · condensation

SCC：Tarjan 与 Kosaraju

有向图按互相可达划分出 strongly connected component。Tarjan 一遍 DFS 靠 dfn 与 low 认出分量的根，Kosaraju 用正反两遍 DFS，缩点后得到一张 DAG。

low-link · block

articulation point 与 bridge

无向图上同一遍 DFS 的 dfn 与 low：判据差一个等号，分别对应删点断开与删边断开；root 另有判法，边栈顺带切出 biconnected component。

2-SAT · implication graph

2-SAT：归约成 SCC 判定

每条子句翻成两条蕴含边，可满足当且仅当没有变量与它的反面落进同一个 SCC；解按分量编号的大小直接读出，全程线性。

相关链接

• 连通性 · 分隔集与 Menger 定理 本站 同一主题的理论侧：拆开两点最少删几个点，与两点间最多几条不相交路。本系列补的是算法侧——怎么一遍 DFS 把割点全找出来。
• 拓扑排序 · Kahn 与 DFS 本站 condensation 缩点后得到的正是一张 DAG，接着能做的事都在这一页：线性化、DAG 上的递推、环检测。
• 四种基本功 · DFS / BFS / 回溯 / 剪枝 本站 low-link 的全部前置知识：DFS 的递归栈、进入与完成两个时刻、以及树边与非树边的区分。
• Depth-First Search and Linear Graph Algorithms epubs.siam.org Tarjan 1972 年的原论文，SCC 与 biconnected component 两个算法出自同一篇，两者共用的正是 dfn / low 这对数字。