记录编号	46686	评测结果	AAAAAAAAAA
题目名称	[顾研NOIP] 旅游电车	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.747 s
提交时间	2012-10-29 12:32:40	内存使用	4.54 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <stack>
using namespace std;

int timnow,waynum[5010],wayto[5010][60],tim[5010],timlow[5010],dad[5010],ysnum[5010];
bool flag,used[5010],used2[5010],insta[5010],ans[5010];
stack<int> sta,sta2;

int findroot(int a)
{
	int pos=a;
	while (dad[pos])
	{
		sta2.push(pos);
		pos=dad[pos];
	}
	while (!sta2.empty())
	{
		dad[sta2.top()]=pos;
		sta2.pop();
	}
	return(pos);
}

void combine(int a,int b)
{
	a=findroot(a);
	b=findroot(b);
	if (ysnum[a]>ysnum[b])
	{
		ysnum[a]+=ysnum[b];
		dad[b]=a;
	}
	else
	{
		ysnum[b]+=ysnum[a];
		dad[a]=b;
	}
}

void tarjan(int pos)
{
	int i,to;
	used[pos]=true;
	insta[pos]=true;
	sta.push(pos);
	tim[pos]=++timnow;
	timlow[pos]=timnow;
	for (i=0;i<waynum[pos];i++)
	{
		to=wayto[pos][i];
		if (!used[to])
		{
			tarjan(to);
			timlow[pos]=min(timlow[pos],timlow[to]);
		}
		else if (insta[to])
		{
			timlow[pos]=min(timlow[pos],tim[to]);
		}
	}
	if (timlow[pos]==tim[pos])
	{
		to=sta.top();
		insta[to]=false;
		sta.pop();
		while (pos!=to)
		{
			combine(pos,to);
			to=sta.top();
			insta[to]=false;
			sta.pop();
		}
	}
}

void dfs(int pos,int jh)
{
	int i,to;
	for (i=0;i<waynum[pos];i++)
	{
		to=wayto[pos][i];
		if (!used[to])
		{
			if (findroot(to)!=jh)
			{
				flag=false;
				break;
			}
			used[to]=true;
			dfs(to,jh);
			if (!flag)
				break;
		}
	}
}

int main(void)
{
	freopen("buss.in","r",stdin);
	freopen("buss.out","w",stdout);
	int i,j,n,m,a,b,temp;
	while (scanf("%d",&n))
	{
		if (n==0)
			break;
		for (i=1;i<=n;i++)
			ysnum[i]=1;
		scanf("%d",&m);
		timnow=0;
		memset(waynum,0,sizeof(waynum));
		memset(wayto,0,sizeof(wayto));
		memset(used,0,sizeof(used));
		memset(used2,0,sizeof(used2));
		memset(dad,0,sizeof(dad));
		memset(ans,0,sizeof(ans));
		for (i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			wayto[a][waynum[a]++]=b;
		}
		for (i=1;i<=n;i++)
			if (!used[i])
				tarjan(i);
		for (i=1;i<=n;i++)
		{
			memset(used,0,sizeof(used));
			temp=findroot(i);
			if (!used2[temp])
			{
				flag=true;
				used2[temp]=true;
				used[i]=true;
				dfs(i,temp);
			}
			if (flag)
			{
				for (j=1;j<=n;j++)
					if (used[j])
						ans[j]=true;
			}
		}
		for (i=1;i<=n;i++)
			if (ans[i])
				cout<<i<<' ';
		cout<<endl;
	}
	return(0);
}