Cod sursa(job #2064951)

Utilizator danny794Dan Danaila danny794 Data 13 noiembrie 2017 08:16:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <set>
#include <vector>

std::ifstream cin("sortaret.in");
std::ofstream cout("sortaret.out");

class Graph {
 public:
  Graph(int n) {
    incoming.resize(n);
    outgoing.resize(n);
    solution.reserve(n);
  }

  void addEdge(int from, int to) {
    incoming[to].insert(from);
    outgoing[from].insert(to);
  }

  void buildSolution() {
    size_t idx;
    for (idx = 0; idx < outgoing.size(); idx++) {
      if (incoming[idx].empty()) {
        solution.emplace_back(idx);
      }
    }
    idx = 0;
    while (idx < solution.size() &&
           solution.size() < outgoing.size()) {
      removeNode(solution[idx]);
      idx++;
    }
  }

  void printSolution() {
    for (const auto& node : solution) {
      cout << (node + 1) << " ";
    }
  }

 private:
  void removeNode(int node) {
    for (const auto& to : outgoing[node]) {
      incoming[to].erase(node);
      if (incoming[to].empty()) {
        solution.emplace_back(to);
      }
    }
    outgoing[node].clear();
  }

  std::vector<std::set<int>> incoming;
  std::vector<std::set<int>> outgoing;
  std::vector<int> solution;
};

int main() {
  int n, m, a, b;
  cin >> n >> m;
  Graph g(n);
  while (m-- > 0) {
    cin >> a >> b;
    g.addEdge(a - 1, b - 1);
  }
  g.buildSolution();
  g.printSolution();
  return 0;
}