记录编号	46068	评测结果	AAAAAAAAAA
题目名称	[顾研NOIP] 旅游电车	最终得分	100
用户昵称	不列颠呆毛	是否通过	通过
代码语言	C++	运行时间	0.736 s
提交时间	2012-10-26 16:40:03	内存使用	3.65 MiB

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

typedef vector<int>::iterator iter;
int n,m,flag[10000],k,ans[10000],s[10000],fin[10000];
vector<int> in[10000],out[10000],fl[10000];
vector<int> que;

int initinal(){
    memset(flag,0,sizeof(flag));
    memset(ans,0,sizeof(ans));
    memset(s,0,sizeof(s));
    memset(fin,0,sizeof(fin));
    k=0;
    for (int i=1; i<=n; i++) in[i].clear();
    for (int i=1; i<=n; i++) out[i].clear();
    for (int i=1; i<=n; i++) fl[i].clear();
    que.clear();
    return 0;
}
int dfs(int x){
    flag[x]=1;
    for (iter i=out[x].begin(); i!=out[x].end(); i++)
	if (!flag[*i]) dfs(*i);
    que.push_back(x);
    return 0;
}

int find(int x,int st){
    flag[x]=1; fl[st].push_back(x); s[x]=k;
    for (iter i=in[x].begin(); i!=in[x].end(); i++)
	if (!flag[*i]) find(*i,st);
    return 0;
}
    	
int main(){
    freopen("buss.in","r",stdin);
    freopen("buss.out","w",stdout);
    while (scanf("%d%d",&n,&m)!=EOF){
    initinal();
    for (int i=1; i<=m; i++){
	int a,b;
	scanf("%d%d",&a,&b);
	out[a].push_back(b);
	in[b].push_back(a);
    }
    for (int i=1; i<=n; i++)
	if (!flag[i]) dfs(i);

    memset(flag,0,sizeof(flag));
    for (int i=1; i<=n; i++)
	if (!flag[*(que.end()-i)]) find(*(que.end()-i),++k);
    
    memset(flag,0,sizeof(flag));
    for (int i=1; i<=n; i++)
	for (iter j=out[i].begin(); j!=out[i].end(); j++)
	    if (s[i]!=s[*j]) flag[i]=1;

    for (int i=1; i<=k; i++)
	for (iter j=fl[i].begin(); j!=fl[i].end(); j++)
	    if (flag[*j]) ans[i]=1;

    for (int i=1; i<=k; i++)
	if (!ans[i])
	    for (iter j=fl[i].begin(); j!=fl[i].end(); j++)
		fin[*j]=1;
    for (int i=1; i<=n; i++) 
	if (fin[i]) printf("%d ",i);
    printf("\n");
    }
    return 0;
}