Cod sursa(job #2037300)

Utilizator sclaiciSebastian Claici sclaici Data 11 octombrie 2017 23:11:23
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

template <class T>
class graph {
 public:
  graph() {}

  void add_edge(T src, T dst) {
    nodes_.insert(src);
    nodes_.insert(dst);
    adjacency_[src].push_back(dst);
  }

  vector<T> topological_sort() {
    unordered_map<T, int> degree;
    for (auto entry : adjacency_) {
      for (auto neigh : entry.second)
        degree[neigh]++;
    }

    queue<T> q;
    for (auto &n : nodes_)
      if (degree[n] == 0)
        q.push(n);

    vector<T> sorted;
    while (!q.empty()) {
      T n = q.front();
      q.pop();
      sorted.push_back(n);

      for (T neigh : adjacency_[n]) {
        degree[neigh]--;
        if (degree[neigh] == 0)
          q.push(neigh);
      }
    }

    return sorted;
  }

 private:
  unordered_set<T> nodes_;
  unordered_map<T, vector<T>> adjacency_;
};

int main() {
  ifstream fin("sortaret.in");
  ofstream fout("sortaret.out");

  int n, m;
  fin >> n >> m;

  graph<int> G;
  for (int i = 0; i < m; ++i) {
    int src, dst;
    fin >> src >> dst;
    G.add_edge(src, dst);
  }
  fin.close();

  auto res = G.topological_sort();
  for (auto x : res)
    fout << x << " ";
  fout << "\n";
  fout.close();

  return 0;
}