记录编号	201567	评测结果	AAAAAAAAAA
题目名称	[顾研NOIP] 旅游电车	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.200 s
提交时间	2015-10-30 20:58:42	内存使用	0.99 MiB

#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 5002
int dfn[maxn],low[maxn],belong[maxn];
int n,m,stak[maxn],top,times,scc,tot,head[maxn];
bool vis[maxn],vist[maxn];
int flag[maxn];
struct dd{
	int begin,end,next;
}jie[50010];
void Clear(){
	memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
	memset(vis,false,sizeof(vis));
	memset(flag,0,sizeof(flag)); memset(head,0,sizeof(head));
	times=0;top=0;scc=0;tot=0;
}
inline int in(){
	int TEMP,EPX;
	TEMP=0;EPX=getchar();
	while(EPX<48||EPX>57)
		EPX=getchar();
	for(;EPX>47&&EPX<58;EPX=getchar())
		TEMP=(TEMP<<3)+(TEMP<<1)+EPX-48;
	return TEMP;
}
void add(int x,int y){
	jie[++tot].begin=x; jie[tot].end=y; jie[tot].next=head[x]; head[x]=tot;
}

void tar(int x){
	dfn[x]=low[x]=++times;vis[x]=1;
	stak[++top]=x;
	for(int i=head[x];i;i=jie[i].next){
		int yu=jie[i].end;
		if(!dfn[yu]){
			tar(yu);
			if(low[yu]<low[x]) low[x]=low[yu];
		}
		else
		 if(vis[yu])
		  if(dfn[yu]<low[x]) low[x]=dfn[yu];
	 }
	if(dfn[x]==low[x]){
		++scc;
		int yu=-1;
		do{
		   yu=stak[top--];vis[yu]=0;
		   belong[yu]=scc;
		}while(yu!=x);
	}
}
bool dfs(int x){
	vist[x]=1;
	for(int i=head[x];i;i=jie[i].next){
		if(vist[jie[i].end]) continue;
		if(belong[x]!=belong[jie[i].end]) return false;
		if(!dfs(jie[i].end)) return false;
	}
	return true;
}
void Judge(){
	for(int i=1;i<=n;++i){
		if(flag[belong[i]]==0){
			memset(vist,0,sizeof(vist));
			if(dfs(i)) {
				flag[belong[i]]=1; printf("%d ",i);
			}
			else flag[belong[i]]=-1;
		}
		else
		 if(flag[belong[i]]==1) printf("%d ",i);
	}
	printf("\n");
}
int main(){
    freopen("buss.in","r",stdin);
	freopen("buss.out","w",stdout);
	while(scanf("%d",&n)&&n){
		 Clear();
		 m=in();
		 for(int i=1;i<=m;++i){
			int x,y; x=in();y=in();
			add(x,y);
		}
		for(int i=1;i<=n;++i) if(!dfn[i]) tar(i);
		Judge();
	}
	return 0;
}