Cod sursa(job #1520246)

Utilizator tudorcomanTudor Coman tudorcoman Data 8 noiembrie 2015 15:41:42
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb

#include <bits/stdc++.h>
using namespace std;

#define push push_back
const int maxN = 50000;
const int maxM = 100000;

vector<int> G[maxN + 2];
deque<int> C;
int N, M, grad[maxN + 2];

int main(void) {
  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w", stdout);
  scanf("%d %d", &N, &M);
  for(register int i = 1; i <= M; ++ i) {
    int a, b;
    scanf("%d %d", &a, &b);
    G[a].push_back(b);
    ++ grad[b];
  }
  for(register int i = 1; i <= N; ++ i)
    if(!grad[i])
      C.push(i);
  for(register int i = 0; i < N; ++ i) {
    int nod = C[i];
    for(auto it = G[nod].begin(); it != G[nod].end(); ++ it)
      if(-- grad[*it] == 0)
        C.push(*it);
  }
  for(register int i = 0; i < N; ++ i)
    printf("%d ", C[i]);
  printf("\n");
  return 0;
}