记录编号	295556	评测结果	AAAAAAAAAA
题目名称	[顾研NOIP] 旅游电车	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.273 s
提交时间	2016-08-13 21:02:08	内存使用	17.40 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500010;
struct edge{
	int to,prev;
	edge():prev(0){}
}e[maxn<<1];
void insert(int,int,int*);
void dfs1(int);
void dfs2(int);
int n,m,last[maxn],relast[maxn],len,tim,belong[maxn],top,b[maxn];
pair<int,int>a[maxn];
int cnt,x,y,d[maxn];
bool vis[maxn]={false};
int main(){
#define MINE
#ifdef MINE
	freopen("buss.in","r",stdin);
	freopen("buss.out","w",stdout);
#endif
	label:
	scanf("%d%d",&n,&m);
	if(!n)return 0;
	len=tim=top=cnt=0;
	memset(last,0,sizeof(last));
	memset(relast,0,sizeof(relast));
	memset(vis,0,sizeof(vis));
	memset(belong,0,sizeof(belong));
	memset(d,0,sizeof(d));
	while(m--){
		scanf("%d%d",&x,&y);
		insert(x,y,last);
		insert(y,x,relast);
	}
	for(int i=1;i<=n;i++)if(!vis[i])dfs1(i);
	for(int i=n;i;i--)if(!belong[b[i]])dfs2(b[i]);
	for(int x=1;x<=n;x++){
		for(int i=last[x];i;i=e[i].prev)if(belong[x]!=belong[e[i].to])d[belong[x]]++;
	}
	for(int i=1;i<=n;i++)if(!d[belong[i]])printf("%d ",i);
	printf("\n");
	goto label;
	return 0;
}
void insert(int x,int y,int *last){
	e[++len].to=y;
	e[len].prev=last[x];
	last[x]=len;
}
void dfs1(int x){
	a[++top]=make_pair(x,last[x]);
	vis[x]=true;
	int i;
	while(top){
		x=a[top].first;
		i=a[top].second;
		while(i&&vis[e[i].to])i=e[i].prev;
		if(i){//扩展
			a[top].second=e[i].prev;
			vis[e[i].to]=true;
			a[++top]=make_pair(e[i].to,last[e[i].to]);
		}
		else{//回溯
			b[++tim]=x;
			top--;
		}
	}
}
void dfs2(int x){
	a[++top]=make_pair(x,relast[x]);
	vis[x]=true;
	belong[x]=++cnt;
	int i;
	while(top){
		x=a[top].first;
		i=a[top].second;
		while(i&&belong[e[i].to])i=e[i].prev;
		if(i){//扩展
			a[top].second=e[i].prev;
			belong[e[i].to]=cnt;
			a[++top]=make_pair(e[i].to,relast[e[i].to]);
		}
		else{//回溯
			top--;
		}
	}
}