Tarjan算法图论全家桶系列--边双联通分量(eDCC)

边双联通分量(eDCC)

定义

在无向图G=(V,E)中，如果删除任意一条边后，子图仍然连通，则称这个子图是边连通的。
边双连通分量（Edge Biconnected Component, eDCC）：图的极大边连通子图。

重要性质：

边双连通分量内部没有割边（桥）
不同的边双连通分量之间通过割边连接
每个节点属于且只属于一个边双连通分量
边双连通分量可以缩点，形成一棵树（每个分量作为一个节点，割边作为树边）

Tarjan算法求边双连通分量

1. 算法核心思想
   Tarjan算法基于深度优先搜索（DFS），在求割边算法的基础上稍作扩展。核心思想是：
   首先找出所有的割边
   然后删除割边，剩下的每个连通块就是一个边双连通分量
   但实际实现中，我们可以在一次DFS中同时完成这两个任务
2. 算法流程
   与求割边类似，但添加了一个栈来存储当前DFS路径上的节点。当发现一个割边时，并不立即弹出节点，而是在DFS回溯时，根据dfn[u]==low[u]条件来识别一个边双连通分量。

// 核心判断条件if(low[u]==dfn[u]){// 发现一个新的边双连通分量++tot;// 分量计数器加1intv=-1;do{v=stk.top();stk.pop();bel[v]=tot;// 标记v属于第tot个分量}while(v!=u);}

模板

说明：void Clear(int _n)初始化，准备输入的图有n个点。void Add(int u,int v),在u,v之间连一条无向边。void Run()运行Tarjan算法求双联通分量。vector<int> Get()：获取bel数组,bel[i]为i点属于的边双联通分量编号

template<intN>structeDCC{//已考虑了含重边的情况vector<pair<int,int>>adj[N];vector<int>stk;vector<int>bel;vector<pair<int,int>>bridge;intdfn[N],low[N];intclk,eid,tot,n;//时间，边编号,边双数量voidAdd(intu,intv){//u,v之间连一条无向边++eid;adj[u].push_back({v,2*eid});adj[v].push_back({u,2*eid+1});}voiddfs(intu,intuk){dfn[u]=low[u]=++clk;stk.push_back(u);for(auto&[to,k]:adj[u]){if(k==(uk^1))continue;//不能走回父亲的边if(dfn[to]==0){dfs(to,k);low[u]=min(low[u],low[to]);if(low[to]>dfn[u])bridge.push_back({u,to});}elselow[u]=min(low[u],dfn[to]);}if(dfn[u]==low[u]){++tot;intv=-1;do{v=stk.back();stk.pop_back();bel[v]=tot;}while(v!=u);}}voidClear(int_n){//开始Add()之前先Clear()n=_n;for(inti=0;i<=_n+3;++i)adj[i].clear();stk.clear();bridge.clear();bel.assign(n+3,0);tot=eid=clk=0;fill(dfn,dfn+5+_n,0);fill(low,low+5+_n,0);}voidRun(){for(inti=1;i<=n;++i)if(dfn[i]==0)dfs(i,-1);}vector<int>Get(){returnbel;}};constintmaxn=2*1e5+20;eDCC<maxn>T;