题解
唯一能解释的图片,黄色代表会执行入栈操作的点
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 son=0;
for(auto next:G[now])
{
if(next==fa)continue;
son++;
if(vis[next]) low[now]=min(low[now],vis[next]);
else
{
ss(next,now);
if(low[next]>=vis[now])
{
cnt++;
int x;
do
{
x=q.top();
ans[cnt].push_back(x);
q.pop();
}while(next!=x);
ans[cnt].push_back(now);
}
else low[now]=low[next];
}
}
if(now==fa&&son==0)
{
ans[++cnt].push_back(now);
q.pop();
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
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;
}
标签:cnt,点双,int,back,P8435,ans,push,now,模板
From: https://www.cnblogs.com/pure4knowledge/p/18032626