Cod sursa(job #1521964)

Utilizator danny794Dan Danaila danny794 Data 11 noiembrie 2015 01:46:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <vector>

#define NMAX 50010

using namespace std;

int N, M, remainingDepency[NMAX];
vector<int> dependency[NMAX];
vector<int> queue;

void readInput() {
  int a, b;
  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w", stdout);
  scanf("%d %d\n", &N, &M);
  for (int i = 0; i < M; i++) {
    scanf("%d %d\n", &a, &b);
    dependency[a].push_back(b);
    remainingDepency[b]++;
  }
}

inline void addToQueue(int index) {
  if (remainingDepency[index] == 0) {
    queue.push_back(index);
    remainingDepency[index] = -1;
    printf("%d ", index);
  }
}

int solve() {
  int index = 0;
  for (int i = 1; i <= N; i++) {
    addToQueue(i);
  }
  while (!queue.empty()) {
    index = queue.back();
    queue.pop_back();
    for (int i = 0; i < dependency[index].size(); i++) {
      int removedDep = dependency[index][i];
      remainingDepency[removedDep]--;
      addToQueue(removedDep);
    }
  }
}

int main() {
  readInput();
  solve();
  return 0;
}