本地RE,提交AC
查看原帖
本地RE,提交AC
767681
catandcode楼主2023/4/9 08:25

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;
}

2023/4/9 08:25
加载中...