v 0. Pasted by slipstak2 as cpp at 2011-01-11 16:29:30 MSK and set expiration to never.

Paste will expire never.

  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. int n;
  6. enum TYPE_VERTEX{WHITE,GRAY,BLACK};
  7. vector<vector<int> > adj;
  8. vector<TYPE_VERTEX> used;
  9.  
  10. void input() {
  11.     cin>>n;
  12.     adj.resize(n);
  13.     used.resize(n,WHITE);
  14.     int next;
  15.     for (int i=0;i<n;i++)
  16.     {
  17.         do
  18.         {
  19.             cin>>next;
  20.             if (next)
  21.                 adj[i].push_back(next-1);
  22.         } while (next);
  23.     }
  24. }
  25. void dfs(int cur, vector<int> &ans) {
  26.     used[cur] = GRAY;
  27.     for (int i=0; i<adj[cur].size(); i++) {
  28.         int next = adj[cur][i];
  29.         // if (used[next] == GRAY) // Circle
  30.         if (used[next] == WHITE)
  31.             dfs(next,ans);
  32.     }
  33.     used[cur] = BLACK;
  34.     ans.push_back(cur);
  35. }
  36. void topological_sort(vector<int> &ans) {
  37.     for (int i=0;i<n;i++) {
  38.         if (used[i] == WHITE) {
  39.             dfs(i,ans);
  40.         }
  41.     }
  42. }
  43. void solve() {
  44.  
  45.     vector<int> ans;
  46.     topological_sort(ans);
  47.     for (int i=n-1;i>=0;i--)
  48.         cout<<ans[i]+1<<' ';
  49. }
  50. int main() {
  51.     /*freopen("input.txt","r",stdin);
  52.     freopen("output.txt","w",stdout);*/
  53.     input();
  54.     solve();
  55.     return 0;
  56. }


Editing is locked.