Tarjan算法图论全家桶--点双联通分量

定义

在无向图G=(V,E)中，如果删除任意一个节点（及其关联的边）后，子图仍然连通，则称这个子图是点连通的。

点双连通分量（Vertex Biconnected Component, vDCC）：图的极大点连通子图。

重要性质：

1. 点双连通分量内部没有割点
2. 不同的点双连通分量之间通过割点连接
3. 一个割点可以属于多个点双连通分量
4. 点双连通分量和割点一起可以构成块-割点树

Tarjan算法求点双连通分量

1. 算法核心思想

Tarjan算法基于深度优先搜索（DFS），是求割点算法的扩展。核心思想是：

1. 在DFS过程中维护一个栈，存储当前搜索路径上的节点
2. 当发现一个割点时，从栈中弹出节点直到当前节点的子节点
3. 弹出的节点与割点一起构成一个点双连通分量
4. 注意：割点不出栈，因为它可能属于多个分量

2. 算法流程

// 核心判断条件if(low[to]>=dfn[u]){// 发现割点u的一个vDCC++tot;// 新增一个点双连通分量intv;do{v=stk.top();stk.pop();Dcc[tot].push_back(v);}while(v!=to);// 弹出直到子节点toDcc[tot].push_back(u);// 割点u也加入分量}

模板

说明:void Run(int _n,vector<int> adj[])传入总点数n，vector<int>[]邻接表adj,运行Tarjan求点双联通分量。vector<int> Dcc[N]Dcc[i]存了编号为i的vDcc内所有的点.

template<intN>structvDCC{intdfn[N],low[N];constvector<int>*adj;vector<int>stk,cut;vector<int>Dcc[N];//1~tot,Dcc[i]，编号为i的vDcc内的点.inttot;//vDcc数量intn,clk,root;voiddfs(intu){dfn[u]=low[u]=++clk;stk.push_back(u);intcnt=0;for(intto:adj[u]){if(dfn[to]==0){dfs(to);low[u]=min(low[u],low[to]);if(low[to]>=dfn[u]){++cnt;++tot;intv;do{v=stk.back();stk.pop_back();Dcc[tot].emplace_back(v);}while(v!=to);Dcc[tot].emplace_back(u);}}elselow[u]=min(low[u],dfn[to]);}if((u!=root&&cnt>=1)||cnt>=2)cut[u]=true;if(cnt==0&&u==root)Dcc[++tot].pb(u);}voidRun(int_n,vector<int>adj[]){n=_n;this->adj=adj;clk=tot=0;fill(dfn,dfn+n+3,0);fill(low,low+n+3,0);stk.clear();cut.assign(n+3,false);for(inti=0;i<=n+3;++i)Dcc[i].clear();for(inti=1;i<=n;++i){if(dfn[i]==0){root=i;dfs(i);}}}};constintmaxn=2*1e5+20;vDCC<maxn>T;