Cod sursa(job #1521962)

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

#define NMAX 50010

using namespace std;

int N, M, remainingDepency[NMAX], removed;
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;
    removed++;
    printf("%d ", index);
  }
}

int solve() {
  int index = 0;
  while (removed < N) {
    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;
}