Cod sursa(job #695765)

Utilizator biroBiro Alexandru biro Data 28 februarie 2012 14:30:47
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <algorithm>
#include <stdio.h>
#include <vector>
#define DIM 50001
#define pb push_back

using namespace std;

int deg[DIM], q[DIM];
vector<int> g[DIM];

int main() {
  freopen ("sortaret.in","r",stdin) ;
  freopen ("sortaret.out","w",stdout) ;
  
  int n , m  ;

  scanf ("%d%d" , &n , &m);
  
  int nr1, nr2 ;
  
  for(int i=1;i<=m ; ++i){
    scanf("%d %d\n", &nr1, &nr2) ;
    g[nr1].pb(nr2) ;
    deg[nr2]++;
  }
  
  vector<int>::iterator it;

  for(int x=1; x<=n; x++) {
    if(deg[x] == 0) {
      q[++q[0]] = x;
    }
    for(int i=1; i<=n; i++) {
      x = q[i];
      for(it=g[x].begin(); it!=g[x].end(); ++it) {
        deg[*it]--;
        if(deg[*it] == 0) {
          q[++q[0]] = *it;
        }
      }
    }
  }

  for (int i=1 ; i<=n ; ++i) {
    printf ("%d " , q[i]) ;
  }

  return 0;
}