80分蒟蒻求助,1个点WA,4个点TLE了
查看原帖
80分蒟蒻求助,1个点WA,4个点TLE了
263594
寻逍遥2006楼主2021/7/30 16:55

不知道在怎么改了

#include <bits/stdc++.h>
using namespace std;
int N,M,i,k,x,y,s=1,l=1;
int cow[10010],like[50010][2],cowgroup[10010][3];
bool vis[10010],inz[10010],ge[10010],w;int dfn[10010],low[10010],ind,zhan[10010],top;
void Tarjan(int x)
{
	dfn[x]=low[x]=++ind;
	zhan[top]=x;inz[x]=true;vis[x]=true;
	top++;
	int k=cow[x];
	while(k!=0)
	{
		if(!vis[like[k][0]])
		{
			Tarjan(like[k][0]);
			low[x]=min(low[x],low[like[k][0]]);
		}
		else if(inz[like[k][0]])
		    low[x]=min(low[x],dfn[like[k][0]]);
		k=like[k][1];
	}
	if(dfn[x]==low[x])
	{
		int j;
		while(zhan[top]!=x)
		{
			cowgroup[l][0]++;
			if(cowgroup[l][2]==0)
			{
				cowgroup[l][2]=cow[zhan[top-1]];
				j=cowgroup[l][2];
			}
			else
			{
				while(like[j][1]!=0)
				{
					j=like[j][1];
				}
		    	like[j][1]=cow[zhan[top-1]];
			}
			cow[zhan[top-1]]=l;
			top--;
		}
		l++;
	}
	return;
}
int main()
{
	cin>>N>>M;
	for(i=1;i<=M;i++)
	{
		cin>>x>>y;
		like[i][0]=y;
		like[i][1]=cow[x];
		cow[x]=i;
	}
	for(i=1;i<=N;i++)
		if(!vis[i])
		   Tarjan(i);
	l--;
	for(i=1;i<=l;i++)
	{
		memset(ge,0,sizeof(ge));
		k=cowgroup[i][2];
		ge[cow[like[k][0]]]=true;
		while(like[k][1]!=0)
		{
			if(ge[cow[like[like[k][1]][0]]]) like[k][1]=like[like[k][1]][1];
			else k=like[k][1];
		    ge[cow[like[like[k][1]][0]]]=true;
		}				
	}
	for(i=1;i<=l;i++)
	{
		k=cowgroup[i][2];
		while(k!=0)
		{
			cowgroup[cow[like[k][0]]][1]++;
			k=like[k][1]; 
		} 
	}
	memset(vis,0,sizeof(vis));
	i=1;
	while(s<l-1)
	{
		w=true;
		if(cowgroup[i][1]==0&&!vis[i])
		{
			vis[i]=true;
			k=cowgroup[i][2];
	    	while(k!=0)
	    	{
	    		if(cow[like[k][0]]!=i) w=false;
	    		cowgroup[cow[like[k][0]]][1]--;
	    		k=like[k][1];
			}
		    if(w)
			{
				cout<<0;
				return 0;
			}
		    s++;
		}
		if(i==l) i=1;
		else i++;
	}
	while(vis[i])
	{
		if(i==l) i=1;
		else i++;
	}
	cout<<cowgroup[i][0];
	return 0;
 }
2021/7/30 16:55
加载中...