更新日志
思路
首先，我们求出原图中所有的桥，然后跑DFS给原图分区。
求桥具体过程：Tarjan求桥
更具体的，我们遍历每一个点，假如这个点没有被分区，那么就从这个点开始深搜。
每一次深搜，都走不是桥的边，那么走到的就都属于一个边双。（很容易证明）
这样，我们把每一次深搜走到的所有点分成一个边双，储存相应信息即可。
细节
提醒一个小点吧，如果你和我一样使用原边编号储存所有桥（详见求桥部分），那么在判断的时候也应该使用原无向边编号。
模板
注：dfs函数的使用详见例题代码
int dcnt;
int dfn[N],low[N];
bool bri[M];
void tarjan(int now,int fed){
dfn[now]=low[now]=++cnt;
for(int e=hd[now];e;e=ne[e]){
int nxt=to[e],eid=(e-1)/2+1;
if(!dfn[nxt]){
tarjan(nxt,eid);
low[now]=min(low[now],low[nxt]);
if(low[nxt]>dfn[now]){
bri[eid]=true;
}
}else if(eid!=fed)low[now]=min(low[now],dfn[nxt]);
}
}
int bcnt;
int bcc[N];
veci nods[N];
void dfs(int now){
bcc[now]=bcnt;
nods[bcnt].push_back(now);
for(int e=hd[now];e;e=ne[e]){
int nxt=to[e],eid=(e-1)/2+1;
if(bcc[nxt]!=0||bri[eid])continue;
dfs(nxt);
}
}
例题
代码
前注：非题解，不做详细讲解
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> veci;
const int N=5e5+5,M=2e6+5;
int n,m;
int cnt;
int hd[N],to[M*2],ne[M*2];
void adde(int u,int v){
to[++cnt]=v;
ne[cnt]=hd[u];
hd[u]=cnt;
}
int dcnt;
int dfn[N],low[N];
bool bri[M];
void tarjan(int now,int fed){
dfn[now]=low[now]=++cnt;
for(int e=hd[now];e;e=ne[e]){
int nxt=to[e],eid=(e-1)/2+1;
if(!dfn[nxt]){
tarjan(nxt,eid);
low[now]=min(low[now],low[nxt]);
if(low[nxt]>dfn[now]){
bri[eid]=true;
}
}else if(eid!=fed)low[now]=min(low[now],dfn[nxt]);
}
}
int bcnt;
int bcc[N];
veci nods[N];
void dfs(int now){
bcc[now]=bcnt;
nods[bcnt].push_back(now);
for(int e=hd[now];e;e=ne[e]){
int nxt=to[e],eid=(e-1)/2+1;
if(bcc[nxt]!=0||bri[eid])continue;
dfs(nxt);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
int a,b;
for(int i=1;i<=m;i++){
cin>>a>>b;
adde(a,b);
adde(b,a);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i,0);
}
for(int i=1;i<=n;i++){
if(!bcc[i]){
++bcnt;
dfs(i);
}
}
cout<<bcnt<<"\n";
for(int i=1;i<=bcnt;i++){
cout<<nods[i].size()<<" ";
for(auto j:nods[i])cout<<j<<" ";
cout<<"\n";
}
return 0;
}