tarjan求点双连通分量-526互联

边双连通分量见tarjan求边双连通分量
部分参考 lyd 《算法竞赛进阶指南》

前置知识

给定无向连通图 \(G=(V,E)\)

割点：若对于 \(x \in V\)，从图中删去 x 及其连边，\(G\) 分裂成两个及以上不相连子图，那么 x 是 \(G\) 的割点
时间戳：在深度优先访问时按照每个节点第一次被访问的时间顺序，依次给予 \(1\) ~ \(N\) 的标记，记为 \(dfn\) 数组。
搜索树：任选一个节点出发深度优先搜索，每个节点访问一次，所有发生递归的边组成的树。
追溯值：记为 \(low\) 数组，定义为以下节点中的最小值：
1.subtree中的节点。
2.通过一条不在搜索树上的边能够到达subtree的节点。
点双连通图：若一张不存在割点的无向连通图。
点双连通分量：简记为 “v-DCC”，表示无向连通图的极大点双连通子图。

追溯值的求法

先令 low[x]=dfn[x]
若在搜索树上，x 为 y 的父节点，则 low[x]=min(low[x],low[y])。
若无向边 (x,y) 不是搜索树上的边，则 low[x]=min(low[x],dfn[y])。

割点的求法

若 x 为割点，则应当满足以下条件：

若 x 不为搜索树的根节点，存在 x 的至少一个子节点 y 满足 dfn[x]<=low[y]。
若 x 为搜索树的根节点，存在 x 的至少两个子节点 y 满足 dfn[x]<=low[y]。

原理：
当 dfn[x]<=low[y] 时，说明 y 及其子树无法通过除了 x 的节点来访问 x 的祖先节点，说明 x 删除后 y 及其子树无法与 x 的祖先连通。特别地，当 x 为根时，x 没有祖先节点，这时存在两个 y 满足条件，可以保证这两个 y 及其子树在去掉 x 之后互相不连通。

例：P3388 【模板】割点（割顶）
模板题

My code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=100009;
const ll N=20009;
ll n,m;
struct edge{
	ll to,nxt;
} e[M<<1];
ll nE,hd[N];
ll dfn[N],low[N],timer;
ll ans[N],cnt;

void add(ll u,ll v){
	e[++nE]=(edge){v,hd[u]};
	hd[u]=nE;
}

void input(){
	cin>>n>>m;
	for(ll i=1;i<=m;i++){
		ll u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
}

void dfs_tarjan(ll u,ll rt){
	ll ch=0;
	low[u]=dfn[u]=++timer;
	for(ll i=hd[u];i;i=e[i].nxt){
		ll v=e[i].to;
		if(!dfn[v]){
			dfs_tarjan(v,rt);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u!=rt) ans[u]=1;
			if(u==rt) ch++;
		}
		low[u]=min(low[u],dfn[v]);
	}
	if(ch>=2&&u==rt) ans[u]=1;
}

void solve(){
	for(ll i=1;i<=n;i++){
		if(!dfn[i]) dfs_tarjan(i,i);
	}
	for(ll i=1;i<=n;i++){
		if(ans[i]){
			cnt++;
		}
	}
	cout<<cnt<<endl;
	for(ll i=1;i<=n;i++){
		if(ans[i]){
			cout<<i<<" ";
		}
	}
}

int main(){
	input();
	solve();
	return 0;
}

点双连通分量的求法

割点可能属于多个点双连通分量

若存在孤立点，则孤立点本身为一个点双连通分量
若不存在孤立点，则点双连通分量大小至少为2

求法：

第一次访问节点 x 时，将 x 入栈
当 dfn[x]<=low[y] 成立时
1. 从栈顶不断弹出节点，直到 y 被弹出
2. 刚才弹出的所有节点与 x 组成一个 dcc

例：P8435 【模板】点双连通分量
模板题

My code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=500009;
const ll M=2000009;
ll n,m;
struct edge{
	ll to,nxt;
} e[M<<1];
ll nE,hd[N];
ll euler,dfn[N],low[N],cut[N];
vector<int> ans[N];
ll nA;
ll stk[N],nS;

void add(ll u,ll v){
	e[++nE]=(edge){v,hd[u]};
	hd[u]=nE;
}

void input(){
	cin>>n>>m;
	for(ll i=1;i<=m;i++){
		ll u,v;
		cin>>u>>v;
		if(u==v) continue;
		add(u,v);
		add(v,u);
	}
}

void dfs_tarjan(ll u,ll rt){
	low[u]=dfn[u]=++euler;
	stk[++nS]=u;
	ll flag=0;
	if(u==rt&&hd[u]==0){
		ans[++nA].push_back(u);
		return;
	}
	for(ll i=hd[u];i;i=e[i].nxt){
		ll v=e[i].to;
		if(!dfn[v]){
			dfs_tarjan(v,rt);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				flag++;
				if(u!=rt&&flag>2) cut[u]=1;
				nA++;
				ll z;
				do{
					z=stk[nS--];
					ans[nA].push_back(z);
				}while(z!=v);
				ans[nA].push_back(u);
			}
		}
		else{
			low[u]=min(low[u],dfn[v]); 
		}
	}
}

void solve(){
	for(ll i=1;i<=n;i++){
		if(!dfn[i]){
			dfs_tarjan(i,i);
		}
	}
	cout<<nA<<endl;
	for(ll i=1;i<=nA;i++){
		cout<<ans[i].size()<<" ";
		for(ll j=0;j<(ll)ans[i].size();j++){
			cout<<ans[i][j]<<" ";
		}
		cout<<endl;
	}
}

int main(){
	input();
	solve();
	return 0;
}

完结撒花thx~

题解分量electricity tarjan