记录编号	44541	评测结果	AAAAAAAAAA
题目名称	[顾研NOIP] 旅游电车	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	1.115 s
提交时间	2012-10-19 08:14:05	内存使用	3.39 MiB

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN=5010;
int N,M,dfn[MAXN],low[MAXN];
vector<int> map[MAXN];
int Index,InStack[MAXN];
stack<int> sat;
set<int> hash,tmp;

void Tarjan(int k)
{
	Index++;dfn[k]=Index,low[k]=Index;
	InStack[k]=1; sat.push(k); int v;
	for(unsigned int i=0;i<map[k].size();i++)
	{
		v=map[k][i];
		if(!dfn[v])
		{
			Tarjan(v); 
			if(low[v]<low[k]) low[k]=low[v];
		} 
		else if(InStack[v] && dfn[v]<low[k]) low[k]=dfn[v];
	}
	if(dfn[k]==low[k])
	{
		int now; tmp.clear();
		do
		{
			now=sat.top(); sat.pop();
			tmp.insert(now); InStack[now]=0;
		}while(now!=k);
		set<int> :: iterator iter=tmp.begin();
		for(;iter!=tmp.end();iter++)
		{
			now=*iter;
			for(unsigned int i=0;i<map[now].size();i++)
				if(tmp.find(map[now][i])==tmp.end()) return;
		}
		for(iter=tmp.begin();iter!=tmp.end();iter++)
			hash.insert(*iter);
	}
}



int main()
{
	freopen("buss.in","r",stdin);
	freopen("buss.out","w",stdout);
	scanf("%d ",&N); int x,y;
	while(N)
	{
		scanf("%d\n",&M); Index=0; hash.clear();
		for(int i=1;i<=N;i++) map[i].clear();
		for(int i=1;i<=M;i++)
		{
			scanf("%d %d\n",&x,&y);
			map[x].push_back(y);
		}
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(InStack,0,sizeof(InStack));
		for(int i=1;i<=N;i++)
		{
			if(dfn[i]) continue;
			Tarjan(i);
		}
		set<int> :: iterator iter=hash.begin();
		for(;iter!=hash.end();iter++)
			printf("%d ",*iter);
		printf("\n");scanf("%d",&N);
	}
	return 0;
}