记录编号	48878	评测结果	AAAAAAAAAA
题目名称	[顾研NOIP] 旅游电车	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	1.038 s
提交时间	2012-11-06 20:21:22	内存使用	3.38 MiB

#include <cstdio>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int N = 5000 + 10;
int n, m, time;
int dfn[N], low[N];
bool l[N];
vector<int> G[N];
stack<int> s;
set<int> t; set<int>::iterator it;
void Tarjan(int u) {
    dfn[u] = low[u] = ++time;
    l[u] = 1;
    s.push(u);
    for(int i=0; i<G[u].size(); i++) {
        int v = G[u][i];
        if(!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(l[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]) {
        set<int> o; int v;
        do {
            l[v = s.top()] = 0;
            o.insert(v);
            s.pop();
        } while(u != v);
        for(it=o.begin(); it!=o.end(); it++)
            for(int i=0; i<G[*it].size(); i++)
                if(o.find(G[*it][i]) == o.end()) return;
        t.insert(o.begin(), o.end());
    }
}
int main() {
    freopen("buss.in", "r", stdin);
    freopen("buss.out", "w", stdout);
    int a, b;
    while(scanf("%d %d", &n, &m) == 2) {
        for(int i=0; i<=n; i++)
            G[i].clear();
        for(int i=0; i<m; i++) {
            scanf("%d %d", &a, &b);
            G[a].push_back(b);
        }
        fill_n(dfn, n+1, 0);
        fill_n(low, n+1, 0);
        fill_n(l, n+1, 0);
        time = 0;
        t.clear();
        for(int i=1; i<=n; i++)
            if(!dfn[i])
                Tarjan(i);
        for(it=t.begin(); it!=t.end(); it++)
            printf("%d ", *it);
        printf("\n");
    }
    return 0;
}