当前位置：首页 > news >正文

Tarjan算法图论全家桶系列--割边(桥)

news 2026/6/30 23:14:16

割边定义

在无向图G=(V,E)中，如果一条边e满足：删除e后，图的连通分量数量增加，则称e为割边（Bridge）。

重要性质：

割边一定是树边（在DFS生成树中的边）
有重边（多重边）的边不可能是割边
割边对应的两个端点中，至少有一个是割点（除非是悬挂边）

Tarjan算法求割边

1. 算法核心思想

Tarjan算法基于深度优先搜索（DFS），与求割点的算法类似，但判断条件有所不同。核心仍然是两个数组：

dfn[u]：节点u的DFS访问顺序（时间戳）
low[u]：从u出发，不经过DFS树中的父节点，能到达的最小dfn值

2. 判断割边的条件

对于一条树边(u, v)（其中u是v的父节点），如果满足：
low[v] > dfn[u]
那么(u, v)是一条割边。

解释：

low[v]表示从v出发（不经过v→u这条边）能到达的最小时间戳
low[v] > dfn[u]意味着v及其后代无法通过任何非树边到达u或u的祖先
因此，如果删除边(u, v)，v所在的子图将与图的其余部分完全断开

模板

说明:Run(int _n,vector<int> adj[])传入总点数n和vector<int>[]邻接表adj，运行tarjan求割边。vector<pair<int,int>> Get()获取所有割边

template<intN>structCut_edge{//不含重边constvector<int>*adj;vector<pair<int,int>>bridge;intdfn[N],low[N];intclk;voiddfs(intu,intfather){dfn[u]=low[u]=++clk;for(intto:adj[u]){if(to==father)continue;//不能走回父亲的边if(dfn[to]==0){dfs(to,u);low[u]=min(low[u],low[to]);if(low[to]>dfn[u])bridge.push_back({u,to});}elselow[u]=min(low[u],dfn[to]);}}voidRun(int_n,vector<int>adj[]){this->adj=adj;clk=0;bridge.clear();fill(dfn,dfn+5+_n,0);fill(low,low+5+_n,0);for(inti=1;i<=_n;++i)if(dfn[i]==0)dfs(i,-1);}vector<pair<int,int>>Get(){returnbridge;}};constintmaxn=2*1e5+20;Cut_edge<maxn>T;