Cod sursa(job #1559514)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 30 decembrie 2015 22:51:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>
#include <list>
#define maxn 50003

using namespace std;

int N,M,Q[maxn];
list <int> G[maxn];
int d[maxn];

int main(){

  freopen("sortaret.in","r",stdin);
  freopen("sortaret.out","w",stdout);

  scanf("%d %d ",&N,&M);
  int x,y;  
  while(M--){
    scanf("%d %d ",&x,&y);
    G[x].push_back(y);
    d[y]++;
  }

  for(x = 1;x <= N;++x)if(d[x] == 0)Q[++Q[0]] = x;
   
  for(x = 1;x <= N;++x){
     y = Q[x];
     for(list <int> :: iterator it = G[y].begin();it != G[y].end();++it){
         
         --d[*it];   
         if(d[*it] == 0)Q[++Q[0]] = *it;

     }
  }

  for(x = 1;x <= N;++x)printf("%d ",Q[x]);
  printf("\n");

  return 0;
}