全wa啦,呜呜呜
查看原帖
全wa啦,呜呜呜
1079845
BHH985211楼主2024/9/26 20:45
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,tim[10005],low[10005],now=1,instk[10005],cnt=0,vis[10005];//时间戳,回溯值,在栈 
stack<int>r;
vector<int>arr[10005];
vector<int>scc[10005];
void put(int x,int y)
{
	for(int i=0;i<arr[x].size();i++)
	{
		if(arr[x][i]==y) return;
	}
	arr[x].push_back(y);
}
void tarjan(int x)
{
	tim[x]=low[x]=now;
	now++;
	r.push(x),instk[x]=1;//入栈,记录
	for(int i=0;i<arr[x].size();i++) 
	{
		int y=arr[x][i];
		if(tim[y]==0)
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(instk[y]) low[x]=min(low[x],tim[y]);
	}
	if(tim[x]==low[x])
	{
		cnt++;
		a=r.top(),r.pop(),instk[a]=0;
		scc[cnt].push_back(a);
		while(a!=x)
		{
			a=r.top(),r.pop(),instk[a]=0;
			scc[cnt].push_back(a);
		}
	}
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
	cin>>a>>b;
	put(a,b);
}
tarjan(1);
cout<<cnt<<endl;
for(int i=1;i<=cnt;i++)
	sort(scc[i].begin(),scc[i].end());
for(int i=1;i<=n;i++)
{
	if(vis[i]==0)
	{
		for(int j=1;j<=cnt;j++)
		{
			if(scc[j][0]==i)
			{
				for(int k=0;k<scc[j].size();k++)
				{
					cout<<scc[j][k]<<" ";
					vis[scc[j][k]]=1;
				}
				cout<<endl;
				break;
			}
		}
	}
}
   return 0;
}
2024/9/26 20:45
加载中...