Cod sursa(job #642419)

Utilizator bmaticanBogdan-Alexandru Matican bmatican Data 1 decembrie 2011 12:19:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <list>
#include <queue>

using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

void solve() {
  int N, M;
  in >> N >> M;
  list<int> edges[N + 1];
  vector<int> indeg(N + 1, 0);

  while (M--) {
    int x, y;
    in >> x >> y;
    edges[x].push_front(y);
    indeg[y]++;
  }

  // build the initial queue
  queue<int> q;
  for (int i = 1; i <= N; ++i) {
    if (indeg[i] == 0) {
      q.push(i);
    }
  }

  // loop through the queue
  list<int> sol;
  while (!q.empty()) {
    int front = q.front();
    q.pop();
    sol.push_back(front);

    for (list<int>::iterator it = edges[front].begin(); it != edges[front].end(); ++it) {
      indeg[*it]--;
      if (indeg[*it] == 0) {
        q.push(*it);
      }
    }
  }

  // print
  for(list<int>::iterator it = sol.begin(); it != sol.end(); ++it) {
    out << *it << (it == sol.end() ? "" : " ");
  }
  out << endl;
}

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