Cod sursa(job #2518050)

Utilizator al3xionescuIonescu Alexandru al3xionescu Data 4 ianuarie 2020 20:18:07
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include<fstream>
#include<set>
#include<vector>
std::ifstream cin("sortaret.in");
std::ofstream cout("sortaret.out");
class Graph {
    std::vector<std::set<int>> incoming;
    std::vector<std::set<int>> outgoing;
    std::vector<int> solution;
    public:
      Graph(int n) {
          incoming.resize(n);
          outgoing.resize(n);
          solution.reserve(n);
      }

      void addEdge(int from, int to) {
          incoming[to].insert(from);
          incoming[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();
        }
};
int main() {
    int a, b, m, n;
    cin >> n >> m;
    Graph g(n);
    while (m-- > 0) {
        cin >> a >> b;
        g.addEdge(a - 1, b - 1);
    }
    g.buildSolution();
    g.printSolution();
    return 0;
}