Cod sursa(job #2524405)

Utilizator greenadexIulia Harasim greenadex Data 15 ianuarie 2020 17:42:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <string>
#include <vector>
#include <unordered_set>

const std::string kInputFileName = "sortaret.in";
const std::string kOutputFileName = "sortaret.out";

class TopologicalSorter {
  public:
    TopologicalSorter(std::vector<std::vector<int>> adj_nodes) :
      adj_nodes_(std::move(adj_nodes)) {}

    std::vector<int> GetTopologicalSorting() {
      for (int node = 0; node < adj_nodes_.size(); node++) {
        if (!visited_nodes_.count(node)) {
          Dfs(node);
        }
      }
      std::vector<int> top_sorting;
      for (int i = adj_nodes_.size() - 1; i >= 0; i--) {
        top_sorting.push_back(reversed_top_sorting_[i]);
      }

      return top_sorting;
    }

  private:
    void Dfs(int node) {
      if (visited_nodes_.count(node)) {
        return;
      }
      visited_nodes_.insert(node);
      for (const int& adj_node : adj_nodes_[node]) {
        Dfs(adj_node);
      }
      reversed_top_sorting_.push_back(node);
    }

    const std::vector<std::vector<int>> adj_nodes_;

    std::unordered_set<int> visited_nodes_;
    std::vector<int> reversed_top_sorting_;
};

int main() {
  std::ifstream fin(kInputFileName);
  std::ofstream fout(kOutputFileName);

  int num_nodes;
  fin >> num_nodes;

  int num_edges;
  fin >> num_edges;

  std::vector<std::vector<int>> adj_nodes(num_nodes, std::vector<int>());

  for (int i = 0; i < num_edges; i++) {
    int start_node;
    int end_node;
    fin >> start_node >> end_node;
    adj_nodes[start_node - 1].push_back(end_node - 1);
  }

  TopologicalSorter sorter(std::move(adj_nodes));
  const auto top_sorting = sorter.GetTopologicalSorting();
  for (const int& node : top_sorting) {
    fout << node + 1 << ' ';
  }

  return 0;
}