Cod sursa(job #1015869)

Utilizator sebii_cSebastian Claici sebii_c Data 25 octombrie 2013 12:55:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

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

    template <class InputIterator>
    explicit graph(InputIterator begin, InputIterator end)
      : nodes(begin, end) {}

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

    vector<T> topological_sort() {
      unordered_map<T, int> in_degree;
      for (auto entry : edges) {
        for (auto neighbour : entry.second) {
          ++in_degree[neighbour];
        }
      }

      queue<T> q;
      for (auto node : nodes)
        if (in_degree[node] == 0)
          q.push(node);

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

        if (edges.count(node) == 0)
          continue;

        for (auto neighbour : edges[node]) {
          --in_degree[neighbour];
          if (in_degree[neighbour] == 0)
            q.push(neighbour);
        }
      }

      for (auto node : nodes)
        if (in_degree[node] != 0)
          return vector<T>();

      return result;
    }

  private:
    unordered_map<T, vector<T>> edges;
    unordered_set<T> nodes;
};

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

  int N, M;
  fin >> N >> M;

  vector<int> v;
  for (int i = 1; i <= N; ++i)
    v.push_back(i);

  graph<int> g(begin(v), end(v));
  for (int i = 0; i < M; ++i) {
    int src, dst;
    fin >> src >> dst;
    g.add_edge(src, dst);
  }

  auto result = g.topological_sort();
  for (auto node : result)
    fout << node << " ";
  fout << "\n";

  return 0;
}