Cod sursa(job #1243924)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 16 octombrie 2014 16:28:49
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <queue>
#include <set>

using namespace std;

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

int main (int argc, char const *argv[]) {
  int n, m;
  in>>n>>m;
  map<int, set<int>> graph;
  map<int, int> incoming;
  vector<int> sorted;
  for (int i = 0; i < m; ++i) {
    int x, y;
    in>>x>>y;
    graph[x].insert(y);
  }
  for (const auto& it : graph) {
    for (const auto& neighbour : it.second) {
      incoming[neighbour]++;
    }
  }
  queue<int> sort_queue;
  for (int i = 1; i <= n; ++i) {
    if(incoming[i] == 0) {
      sort_queue.push(i);
    }
  }
  while (!sort_queue.empty()) {
    int current = sort_queue.front();
    sort_queue.pop();
    sorted.push_back(current);
    for (const auto& neighbour : graph[current]) {
      if ((--incoming[neighbour]) == 0) {
        sort_queue.push(neighbour);
      }
    }
  }
  for (const auto& x : sorted) {
    out<<x<<" ";
  }
  return 0;
}