记录编号	263562	评测结果	AAAAAAAAAA
题目名称	[顾研NOIP] 旅游电车	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.330 s
提交时间	2016-05-25 16:41:28	内存使用	0.46 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<stack>
#include<cstring>
using namespace std;
const int maxn=5005;
vector<int> f[maxn];
int pre[maxn],low[maxn],scc[maxn],dfs_clock,cnt;
stack<int> S;
int ans[maxn];
bool vis[maxn];
void dfs(int u)
{
    pre[u]=low[u]= ++dfs_clock;
    S.push(u);
    for(int i=0;i<f[u].size();i++)
    {
        int v=f[u][i];
        if(!pre[v])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!scc[v])
        {
            low[u]=min(low[u],pre[v]);
        }
    }
    if(low[u]==pre[u])
    {
        cnt++;
        for(;;)
        {
            int x=S.top();
            S.pop();
            scc[x]=cnt;
            if(x==u) break;
        }
    }
}
void find_scc(int n)
{
    dfs_clock=cnt=0;
    memset(scc,0,sizeof(scc));
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=n;i++)
    {
        if(!pre[i]) dfs(i);
    }
}
bool use[maxn];
bool find(int x)
{
    use[x]=true;
    for(int i=0;i<f[x].size();i++)
    {
        if(use[f[x][i]]) continue;
        if(scc[f[x][i]]!=scc[x]) return false;
        if(!find(f[x][i])) return false;
    }
    return true;
}
int main()
{
    freopen("buss.in","r",stdin);
    freopen("buss.out","w",stdout);
    int n,x,y,m;
    while(scanf("%d",&n)&&n!=0)
    {
        memset(pre,0,sizeof(pre));
        memset(low,0,sizeof(low));
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=n;i++) f[i].clear();
        while (!S.empty()) S.pop();
        cnt=0;
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            f[x].push_back(y);
        }
        find_scc(n);
        for(int i=1;i<=n;i++)
        {
            if(ans[scc[i]]==0)
            {
                memset(use,false,sizeof(use));
                if(find(i))
                {
                    ans[scc[i]]=1;
                    printf("%d ",i);
                }
                else ans[scc[i]]=-1;
            }
            else if(ans[scc[i]]==1) printf("%d ",i);
        }
        cout<<endl;
    }
    return 0;
}