Advertisement
Guest User

Untitled

a guest
Feb 19th, 2015
412
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <deque>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <iomanip>
  18. #include <vector>
  19.  
  20. #define fst first
  21. #define snd second
  22. #define all(x) (x).begin(), (x).end()
  23. #define clr(a, v) memset( a , v , sizeof(a) )
  24. #define pb push_back
  25. #define mp make_pair
  26. #define sz size()
  27. #define FORN( i , s , n ) for( int i = (s) ; i < (n) ; i++ )
  28. #define FOR( i , n ) FORN( i , 0 , n )
  29. #define FORIT( i , x ) for( typeof x.begin() i = x.begin() ; i != x.end() ; i++ )
  30. #define trace(x)    cerr << #x << ": " << x << endl;
  31. #define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  32. #define read ios::sync_with_stdio(false)
  33.  
  34. using namespace std;
  35.  
  36. typedef long long int64;
  37. typedef vector <int> vi;
  38. typedef pair <int,int> ii;
  39. typedef vector <string> vs;
  40. typedef vector <ii> vii;
  41.  
  42. vi adj  [2005];
  43.  
  44. int vis [2005];
  45. int num [2005];
  46. int low [2005];
  47. int comp[2005];
  48.  
  49. int indegree [2005];
  50. int S[2005];
  51. int ts;
  52. int contn, compcont;
  53.  
  54. void dfs(int v){
  55.     num[v] = low[v] = contn++;
  56.     vis[v] = 1;
  57.     S[ts++] = v;
  58.     FOR(i,adj[v].sz){
  59.         int u = adj[v][i];
  60.         if ( num[u] == -1 ) dfs(u);
  61.         if ( vis[u] ) low[v] = min(low[v],low[u]);
  62.     }
  63.     if ( low[v] == num[v] ){
  64.         while(1){
  65.             int u = S[ts-1]; ts--;
  66.             comp[u] = compcont;
  67.             vis[u]  = 0;
  68.             if ( u==v ) break;
  69.         }
  70.         compcont++;
  71.     }
  72. }
  73.  
  74. int main(){
  75.     read;
  76.     int N,v;
  77.     cin>>N;
  78.     FOR(i,N)
  79.         while(cin>>v and v)
  80.             adj[i].pb(v-1);
  81.  
  82.     contn = compcont = 0;
  83.     FOR(i,N) {vis[i]=0; num[i]=-1;}
  84.     ts = 0;
  85.     FOR(i,N) if (num[i]==-1) dfs(i);
  86.     FOR(i,compcont) indegree[i]=0;
  87.  
  88.     FOR(i,N)
  89.         FOR(j,adj[i].sz) if ( comp[i]!=comp[adj[i][j]] ) indegree[comp[adj[i][j]]]++;
  90.  
  91.     int one = 0, SCC =-1;
  92.     FOR(i,compcont) if ( indegree[i]==0 ) {one++;SCC=i;}
  93.  
  94.     if(one==1)
  95.         FOR(i,N) if ( comp[i]==SCC ) cout<<i+1<<" ";
  96.  
  97.     cout<<0<<endl;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement