48分样例4过不了求助
查看原帖
48分样例4过不了求助
1065103
Atri_Lobato楼主2024/8/12 20:55
#include<iostream>
#include<vector>
using namespace std;
int n,m;
vector<int> pic[2000005];
void init()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==y)
		continue;
		pic[x].push_back(y);
		pic[y].push_back(x);
	}
}
int order=0;
int dfn[2000005];
int low[2000005];
int Stack[2000005];
int top=0;
int cnt=0;
int root;
vector<int> double_connected[2000005];
void Tarjan(int now,int father)
{
	order++;
	dfn[now]=order;
	low[now]=order;
	top++;
	Stack[top]=now;
	for(int i=0;i<pic[now].size();i++)
	{
		int next=pic[now][i];
		if(dfn[next]==0)
		{
			Tarjan(next,now);
			low[now]=min(low[now],low[next]);
			if(dfn[now]<=low[next])
			{
				cnt++;
				while(Stack[top]!=next)
				{
					double_connected[cnt].push_back(Stack[top]);
					top--;
				}
				double_connected[cnt].push_back(Stack[top]);
				top--;
				double_connected[cnt].push_back(Stack[top]);
			}
		}
		else// if(next!=father)
		{
			low[now]=min(low[now],dfn[next]);
		}
	}
	if(now==root&&pic[now].size()==0)
	{
		cnt++;
		double_connected[cnt].push_back(now);
	}
}
int main()
{
	init();
	for(int i=1;i<=n;i++)
	{
		if(dfn[i]==0)
		{
//			top=0;
			root=i;
			Tarjan(i,0);
		}
		
	}
	cout<<cnt<<endl;
	for(int i=1;i<=cnt;i++)
	{
		printf("%d ",double_connected[i].size());
		for(int q=0;q<double_connected[i].size();q++)
		{
			printf("%d ",double_connected[i][q]);
		}
		printf("\n");
	}
	return 0;
}
2024/8/12 20:55
加载中...