fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 1000
  4. vector<int>edgelist[MAX];
  5. int n,m,i;
  6. int main(){
  7.     //freopen("in.txt","r",stdin);
  8.     //freopen("out.txt","w",stdout);
  9.     while(scanf("%d%d",&n,&m)==2&&n+m!=0){
  10.         for(i=0;i<m;i++){
  11.             int x,y;
  12.             scanf("%d%d",&x,&y);
  13.             edgelist[x].push_back(y);
  14.         }
  15.         vector<int>in(n+1,0);
  16.         for(i=1;i<=n;i++){
  17.             for(int j=0;j<edgelist[i].size();j++)in[edgelist[i][j]]++;
  18.         }
  19.         queue<int>q;
  20.         for(i=1;i<=n;i++){
  21.             if(in[i]==0)q.push(i);
  22.         }
  23.         vector<int>top_sort;
  24.         vector<int>visited(n+1,0);
  25.         while(!q.empty()){
  26.             int u=q.front();
  27.             q.pop();
  28.             top_sort.push_back(u);
  29.             for(i=0;i<edgelist[u].size();i++){
  30.                 int v=edgelist[u][i];
  31.                 --in[v];
  32.                 if(in[v]==0&&visited[v]!=1){
  33.                     q.push(v);
  34.                     visited[v]=1;
  35.                 }
  36.             }
  37.         }
  38.         for(i=0;i<top_sort.size();i++){
  39.             printf("%d",top_sort[i]);
  40.             if(i!=top_sort.size()-1)printf(" ");
  41.         }
  42.         printf("\n");
  43.         for(i=0;i<n;i++)edgelist[i].clear();
  44.     }
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
5 4
1 2
2 3
1 3
1 5
0 0
stdout
copy 
1 4 2 5 3
https://ideone.com/tOLieT
language:
C++14 (gcc 8.3)
created:
8 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!