92求调,wa#6 #7
查看原帖
92求调,wa#6 #7
467683
return_CE楼主2022/11/20 21:42

调了一个小时还是不知道为啥错了

#include<bits/stdc++.h>
using namespace std;
int n,m,h[10015],cnt,tot=0,t;
int dfn[10015],low[10015]; 
int all[10015],belon[10015];
bool v[10015];
stack <int> q;
struct point 
{
	int to,nex;
}edg[50010];

void add(int x,int y)
{
	edg[++cnt].to=y;
	edg[cnt].nex=h[x];
	h[x]=cnt;
}
void tarjan(int p)
{
	dfn[p]=++t;low[p]=t;
	v[p]=1;
	q.push(p);
	for(int i=h[p];i;i=edg[i].nex )
	{
		int to=edg[i].to;
		if(!dfn[to])
		{
			tarjan(to);
			low[p]=min(low[p],low[to]);
		}
		else if(v[to])low[p]=min(low[p],low[to]);
	}
	if(low[p]==dfn[p])
	{
		tot++;
		while(1)
		{
			int y=q.top();
			q.pop();
			all[tot]++;
			belon[y]=tot;
			v[y]=0;
			if(p==y) break;
		}
		
	}
}

int main()
{
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		add(x,y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i);
	}
//	if(tot==1)
//	{
//		cout<<n;
//		return 0;
//	}
	int du[10005];
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=h[i];j;j=edg[j].nex )
		{
			int to=edg[j].to;
			if(belon[to]!=belon[i])
			{
				du[belon[i]]++;
			}
		}
	}
	for(int i=1;i<=tot;i++)
	{
		if(du[i]==0)
		{
			if(ans)
			{
				cout<<"0";
				return 0;
			}
			ans=i;
		}
	}
	cout<<all[ans];
	return 0;
}
2022/11/20 21:42
加载中...