Cod sursa(job #2060802)

Utilizator GagosGagos Radu Vasile Gagos Data 8 noiembrie 2017 18:47:52
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <cstdio>
#include <set>
#include <stack>
#include <vector>

using namespace std;

vector<set<int>> read_graph() {
  freopen("sortaret.in", "r", stdin);

  int num_nodes, num_links;
  scanf("%d %d", &num_nodes, &num_links);

  vector<set<int>> graph(num_nodes + 1);

  for (int i = 0; i < num_links; ++i) {
    int from, to;
    scanf("%d %d", &from, &to);

    graph[from].insert(to);
  }

  fclose(stdin);

  return graph;
}

vector<int> toposort(vector<set<int>>& graph) {
  set<int> visited;
  set<int> dfs_full_stack_dups;
  vector<int> sorted;

  for (int node = 1; node < graph.size(); ++node) {
    if (visited.find(node) != visited.end()) {
      continue;
    }

    stack<int> dfs_stack;
    stack<int> dfs_full_stack;

    dfs_stack.push(node);
    dfs_full_stack.push(node);
    while (!dfs_stack.empty()) {
      int current_node = dfs_stack.top();

      dfs_stack.pop();
      visited.insert(current_node);

      for (auto node_to_visit_it = graph[current_node].begin();
          node_to_visit_it != graph[current_node].end();
          ++node_to_visit_it) {
        if (visited.find(*node_to_visit_it) == visited.end()) {
          dfs_stack.push(*node_to_visit_it);
          dfs_full_stack.push(*node_to_visit_it);
        }
      }
    }

    while (!dfs_full_stack.empty()) {
      int top = dfs_full_stack.top();

      dfs_full_stack.pop();
      if (dfs_full_stack_dups.find(top) == dfs_full_stack_dups.end()) {
        sorted.push_back(top);
        dfs_full_stack_dups.insert(top);
      }
    }
  }

  return sorted;
}

void write_sorted_list(vector<int>& sorted) {
  freopen("sortaret.out", "w", stdout);

  for (auto node_rit = sorted.rbegin(); node_rit != sorted.rend(); ++node_rit) {
    printf("%d ", *node_rit);
  }
  printf("\n");

  fclose(stdout);
}

int main() {
  vector<set<int>> graph = read_graph();
  vector<int> sorted = toposort(graph);
  write_sorted_list(sorted);

  return 0;
}