记录编号	45816	评测结果	AAAAAAAAAA
题目名称	[顾研NOIP] 旅游电车	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	1.105 s
提交时间	2012-10-25 15:58:31	内存使用	2.71 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];
int Index,InStack[MAXN];
stack<int>sat;
vector<int> map[MAXN];
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])
				Tarjan(i);
		}
		set<int> :: iterator iter=hash.begin();
        for(;iter!=hash.end();iter++)
            printf("%d ",*iter);
        printf("\n");scanf("%d",&N);
    }
    return 0;
}