catandcode @ 2023-04-09 08:25:37
rt
#include<bits/stdc++.h>
#define ld long double
#define ll long long
using namespace std;
int cnt,tim,n,m,dfn[500005],low[500005],q[500005],tail;
vector<pair<int,int> > path[500005];
vector<int> dcc[500005];
void form(int now)
{
++cnt;
int x;
do
{
x=q[tail--];
dcc[cnt].push_back(x);
}while(x!=now);
}
void tarjan(int now,int num)
{
q[++tail]=now,dfn[now]=low[now]=++tim;
for(int i=0;i<path[now].size();++i)
{
if(path[now][i].second==num) continue;
int nxt=path[now][i].first;
if(!dfn[nxt])
{
tarjan(nxt,path[now][i].second);
low[now]=min(low[now],low[nxt]);
if(low[nxt]>dfn[now]) form(nxt);
}
else low[now]=min(low[now],dfn[nxt]);
}
if(!num) form(now);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i=1;i<=m;++i)
{
int a,b;
cin>>a>>b;
path[a].push_back(make_pair(b,i));
path[b].push_back(make_pair(a,i));
}
for(int i=1;i<=n;++i)
{
tail=0;
if(!dfn[i])
tarjan(i,0);
}
cout<<cnt<<endl;
for(int i=1;i<=cnt;++i)
{
cout<<dcc[i].size()<<' ';
for(int j=0;j<dcc[i].size();++j)
cout<<dcc[i][j]<<' ';
cout<<endl;
}
return 0;
}
by syta @ 2023-04-09 09:04:48
本地开无限栈了吗(
by catandcode @ 2023-04-09 15:09:21
@syta ?您的意思是什么?没太理解。
by catandcode @ 2023-04-09 15:30:47
@syta 去搜了一下,解决了,谢谢您。
by syta @ 2023-04-09 15:41:18
@catandcode 不用谢捏!~