fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 111111;
  5. vector<int>matrix[MAX];
  6. int inDegree [MAX];
  7.  
  8.  
  9.  
  10. int main ()
  11. {
  12.     ios::sync_with_stdio(false);
  13.     memset(inDegree, 0, sizeof(inDegree));
  14.  
  15.     int edges, a, b, vertex, cnt=0;
  16.     cin>>vertex>>edges;
  17.  
  18.     while(edges--)
  19.     {
  20.         cin>>a>>b;
  21.         matrix [a].push_back (b);
  22.         inDegree[b]++;
  23.     }
  24.  
  25.     queue<int>Q;
  26.     vector<int> sortedList;
  27.  
  28.     for(int i=1; i<=vertex; i++)
  29.     {
  30.         if(inDegree[i]==0)  Q.push(i);
  31.     }
  32.  
  33.     while(!Q.empty())
  34.     {
  35.         int u = Q.front ();
  36.         Q.pop ();
  37.  
  38.         sortedList.push_back(u);
  39.  
  40.         for(int i=0; i<matrix[u].size(); i++)
  41.         {
  42.             inDegree[matrix [u][i]]--;
  43.             if(inDegree[matrix[u][i]]==0)  Q.push (matrix[u][i]);
  44.         }
  45.         cnt++;
  46.     }
  47.  
  48.     if(cnt!=vertex) cout<<"Sandro fails.\n";
  49.     else
  50.     {
  51.        for(unsigned int i=0; i<sortedList.size (); i++)
  52.        {
  53.            cout<<sortedList [i]<<" ";
  54.        }
  55.     }
  56.  
  57.  
  58.     return 0;
  59. }
  60.  
  61.  
Success #stdin #stdout 0s 19104KB
comments (?)
stdin
copy 
8 9
1 4
1 2
4 2
4 3
3 2
5 2
3 5
8 2
8 6
stdout
copy 
1 7 8 4 6 3 5 2
https://ideone.com/Fhk6vM
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!