记录编号	123124	评测结果	AAAAAAAAAA
题目名称	[顾研NOIP] 旅游电车	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.533 s
提交时间	2014-09-25 21:09:15	内存使用	0.46 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <iterator>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============

//==============var declaration=================
const int MAXN=5010;
vector <int> Edge[MAXN];
stack <int> S;
int n,m;
int scc[MAXN],scc_cnt=0,Index=0,low[MAXN],pre[MAXN],cons[MAXN];
bool ins[MAXN],vis[MAXN];
//==============function declaration============
void tarjan(int x);
bool dfs(int x);
//==============main code=======================
int main()
{  
  string FileName="buss";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
#ifdef DEBUG  
  system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
  clock_t Start_Time=clock();
#endif    
  while (scanf("%d",&n)&&n){
    For(i,1,n)
      Edge[i].clear();
    scanf("%d",&m);
    For(i,1,m){
      int s,e;
      scanf("%d%d",&s,&e);
      Edge[s].push_back(e);
    } 
    memset(pre,0,sizeof(pre));
    memset(low,0,sizeof(low));
    memset(ins,false,sizeof(ins));
    memset(scc,0,sizeof(scc));
    memset(cons,0,sizeof(cons));
    while (!S.empty()) S.pop();scc_cnt=0;
    Index=0;
    For(i,1,n)
      if (!pre[i])
        tarjan(i);
    //cons==0:not done yet 1:OK -1:Fail
    For(i,1,n)
      if (cons[scc[i]]==0){
        memset(vis,false,sizeof(vis));
        if (dfs(i)){
          cons[scc[i]]=1;
          pritnf("%d ",i);
        }
        else
          cons[scc[i]]=-1;
      }
      else if (cons[scc[i]]==1)
        printf("%d ",i);
    printf("\n");
  }
#ifdef DEBUG  
  clock_t End_Time=clock();
  printf("\n\nTime Used: %.4lf Ms\n",double(End_Time-Start_Time)/CLOCKS_PER_SEC);
#endif    
  return 0;
}
//================fuction code====================
void tarjan(int x){
  pre[x]=low[x]=++Index;
  S.push(x);ins[x]=true;
  int siz=Edge[x].size()-1;
  For(i,0,siz){
    int &e=Edge[x][i];
    if (!pre[e]){
      tarjan(e);
      low[x]=min(low[x],low[e]);
    }
    else if (ins[e])
      low[x]=min(low[x],pre[e]);
  }
  if (pre[x]==low[x]){
    scc_cnt++;
    int v=-1;
    do{
      v=S.top();S.pop();
      ins[v]=false;
      scc[v]=scc_cnt;
    }while (v!=x);
  }
}
bool dfs(int x){
  vis[x]=true;
  int siz=Edge[x].size()-1;
  For(i,0,siz){
    int &e=Edge[x][i];
    if (vis[e]) continue;
    if (scc[e]!=scc[x])
      return false;
    if (!dfs(e))
      return false;
  }
  return true;
}