记录编号	46564	评测结果	AAAAAAAAAA
题目名称	[顾研NOIP] 旅游电车	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.551 s
提交时间	2012-10-28 17:27:58	内存使用	3.39 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int n,m,Index=0,dfn[5005]={0},low[5005]={0};
vector<int>con[5005];
stack<int>q;
vector<int>ans,num;
bool used[5005]={0},uu[5005]={0},use[5005]={0};;
void tarjan(int x);
int main()
{
	freopen ("buss.in","r",stdin);
	freopen ("buss.out","w",stdout);
	while (cin>>n>>m)
	{
		if (n==0)
			break;
		for (int i=0;i<=n;i++)
		{
			con[i].clear();uu[i]=0;
			dfn[i]=0;low[i]=0;used[i]=0;
		}
		ans.clear();
		Index=0;
		while (q.size())
			q.pop();
		int a,b;
		for (int i=0;i<m;i++)
		{
			scanf("%d%d",&a,&b);
			con[a].push_back(b);
		}
		for (int i=1;i<=n;i++)
		{
			if (!used[i])
			{
				tarjan(i);
			}
		}
		sort(ans.begin(),ans.end());
		for (int i=0;i<ans.size();i++)
			printf("%d ",ans[i]);
		printf("\n");
	}
	return 0;
}

void tarjan(int x)
{
	dfn[x]=low[x]=++Index;
	q.push(x);
	used[x]=1;
	uu[x]=1;
	for (int i=0;i<con[x].size();i++)
	{
		if (!used[con[x][i]])
		{
			tarjan(con[x][i]);
			low[x]=min(low[x],low[con[x][i]]);
		}
		else
		{
			if (uu[con[x][i]])
			{
				low[x]=min(low[x],dfn[con[x][i]]);
			}
		}
	}
	if (dfn[x]==low[x])
	{
		memset(use,0,sizeof(use));
		num.clear();
		while (q.top()!=x&&q.size())
		{
			num.push_back(q.top());
			uu[q.top()]=0;
			use[q.top()]=1;
			q.pop();
		}
		if (q.size())
		{
			uu[q.top()]=0;
			use[q.top()]=1;
			num.push_back(q.top());
			q.pop();
		}
		bool tmp=0;
		for (int i=0;i<num.size();i++)
		{
			for (int j=0;j<con[num[i]].size();j++)
			{
				if (!use[con[num[i]][j]])
				{
					tmp=1;
					break;
				}
			}
			if (tmp)
				break;
		}
		if (!tmp)
		{
			for (int i=0;i<num.size();i++)
				ans.push_back(num[i]);
		}
		
	} 
}
/*
bool check(int x)
{
	for (int i=0;i<=n;i++)
		used[i]=0;
	int w[5005]={0};
	int tou,wei;
	tou=wei=0;
	w[0]=x;
	used[x]=1;
	while (tou<=wei)
	{
		for (int i=0;i<con[w[tou]].size();i++)
		{
			int j;
			j=con[w[tou]][i];
			if (!used[j])
			{
				if (use[w[tou]][j])
				{
					wei++;
					w[wei]=j;
					used[j]=1;
				}
				else
					return false;
			}
		}
		tou++;
	}
	return true;
}*/