Cod sursa(job #2059062)

Utilizator GagosGagos Radu Vasile Gagos Data 6 noiembrie 2017 17:01:40
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 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) {
  stack<int> dfs_stack;
  set<int> visited;
  vector<int> sorted;

  dfs_stack.push(1);
  visited.insert(1);
  while (!dfs_stack.empty()) {
    int current_node = dfs_stack.top();
    dfs_stack.pop();

    if (!graph[current_node].empty()) {
      for (auto node_to_visit : graph[current_node]) {
        if (visited.find(node_to_visit) == visited.end()) {
          visited.insert(node_to_visit);
          dfs_stack.push(node_to_visit);
        }
      }
    }

    sorted.push_back(current_node);
  }

  return sorted;
}

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

  for (auto node : sorted) {
    printf("%d ", node);
  }
  printf("\n");

  fclose(stdout);
}

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

  return 0;
}