)
割边定义
在无向图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;
