题解
和点双连通分量不同在于
点双联通分量:分量内任意两点之间至少有两条独立路径可走,两条路径所经过的点除了起点和终点都不同
边双连通分量:分量内任意两点之间至少有两条独立路径可走,两条路径所经过的边都不同(包括重边)
用这个图依然可以解释
code
#include<bits/stdc++.h>
using namespace std;
int vis[500005]={0};
int low[500005]={0};
stack<int> q;
vector<int> ans[500005];
vector<int> G[500005];
int len=0;
int cnt=0;
void ss(int now,int fa)
{
//cout<<now<<endl;
vis[now]=++len;
low[now]=len;
q.push(now);
int way=0;
for(auto next:G[now])
{
if(next==fa&&!way)
{
way++;
continue;
}
if(vis[next]) low[now]=min(low[now],vis[next]);
else
{
ss(next,now);
low[now]=min(low[now],low[next]);
}
}
if(vis[now]==low[now])
{
int x;
cnt++;
do
{
x=q.top();
ans[cnt].push_back(x);
q.pop();
}while(x!=now);
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
if(x==y)continue;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!vis[i]) ss(i,i);
cout<<cnt<<endl;
for(int i=1;i<=cnt;i++)
{
cout<<ans[i].size()<<" ";
for(auto val:ans[i]) cout<<val<<" ";
puts("");
}
return 0;
}
标签:连通,边双,int,路径,P8436,500005,模板,分量
From: https://www.cnblogs.com/pure4knowledge/p/18032679