双连通分量

无向图中，删除一个点会使连通块数增加的点称为割点；删除一条边使图更不连通的边称为桥。点双连通分量（v-BCC）是没有割点影响内部连通性的极大子图，割点可属于多个点双。

Tarjan 的 dfn 与 low

dfn[u] 是 DFS 访问次序；low[u] 是 u 子树能经树边和一条返祖边到达的最小 dfn。遍历树边 u→v 后，若 low[v]≥dfn[u]，则从边栈弹出直到 (u,v)，这些边及端点构成一个点双；非根 u 是割点。根有至少两个 DFS 子树时才是割点。

void dfs(int u,int pe){
 dfn[u]=low[u]=++tim;
 for(auto [v,id]:g[u]) if(id!=pe){
  if(!dfn[v]){ st.push(id); dfs(v,id); low[u]=min(low[u],low[v]);
   if(low[v]>=dfn[u]){ vector<int> comp; /* 弹栈至 id，收集端点 */ }
  }else if(dfn[v]<dfn[u]) low[u]=min(low[u],dfn[v]),st.push(id);
 }
}

桥与缩点

树边满足 low[v]>dfn[u] 时是桥。边双连通分量可通过删桥后 DFS 得到，缩点后形成一棵桥树；点双与割点可构成圆方树（块割树）。

Tarjan 算法每条边、点仅处理常数次，时间 O(n+m)、空间 O(n+m)。无向边应带边编号，跳过父边而非父节点，才能正确处理重边。整理自 XOJ《双连通分量》。