边双连通分量见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] 成立时
- 从栈顶不断弹出节点，直到 y 被弹出
- 刚才弹出的所有节点与 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~
标签：rt,tarjan,ll,连通,节点,dfn,low,求点 From： https://www.cnblogs.com/lemon-cyy/p/17675024.html