Cod sursa(job #2061550)

Utilizator GagosGagos Radu Vasile Gagos Data 9 noiembrie 2017 14:10:22
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

class topological_sorter {
  private:
    int num_nodes;
    vector<unordered_set<int>> graph;
    vector<bool> visited_nodes;
    vector<int> sorted_nodes;

    void dfs(int node);

  public:
    const vector<int>& get_sorted_nodes() const;

    void read_graph(string input_file_name);

    void sort();

    void write_sorted_nodes(string output_file_name);
};

inline const vector<int>& topological_sorter::get_sorted_nodes() const {
  return sorted_nodes;
}

void topological_sorter::read_graph(string input_file_name) {
  ifstream input_file(input_file_name);
  int num_links;

  input_file >> num_nodes >> num_links;
  vector<unordered_set<int>> tmp_graph(num_nodes + 1);
  vector<bool> tmp_visited_nodes(num_nodes);

  for (int i = 0; i < num_links; ++i) {
    int from, to;
    input_file >> from >> to;
    tmp_graph[from].insert(to);
  }

  input_file.close();
  graph = tmp_graph;
  visited_nodes = tmp_visited_nodes;
}

void topological_sorter::sort() {
  for (int node = 1; node <= num_nodes; ++node) {
    if (!visited_nodes[node]) {
      dfs(node);
    }
  }
}

void topological_sorter::dfs(int node) {
  visited_nodes[node] = true;
  for (auto node_it = graph[node].begin(); node_it != graph[node].end(); ++node_it) {
    if (!visited_nodes[*node_it]) {
      dfs(*node_it);
    }
  }
  sorted_nodes.push_back(node);
}

void topological_sorter::write_sorted_nodes(string output_file_name) {
  ofstream output_file(output_file_name);

  for (auto node_it = sorted_nodes.rbegin(); node_it != sorted_nodes.rend(); ++node_it) {
    output_file << *node_it << ' ';
  }
  output_file << endl;

  output_file.close();
}

int main() {
  topological_sorter sorter;

  sorter.read_graph("sortaret.in");
  sorter.sort();
  sorter.write_sorted_nodes("sortaret.out");

  return 0;
}