Cod sursa(job #2456724)

Utilizator igsifvevc avb igsi Data 15 septembrie 2019 12:47:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <algorithm>
#include <fstream>
#include <functional>
#include <iterator>
#include <vector>

using graph = std::vector<std::vector<int>>;

std::vector<int> solve(const graph &G) {
  std::vector<int> topo;
  std::vector<bool> seen(G.size(), false);

  std::function<void(const int)> dfs = [&topo, &seen, &G, &dfs](const int v) {
    seen[v] = true;

    for (auto u : G[v]) {
      if (!seen[u]) {
        dfs(u);
      }
    }

    topo.push_back(v);
  };

  for (int v = 1; v < G.size(); v++) {
    if (!seen[v]) {
      dfs(v);
    }
  }

  return std::vector<int>(topo.rbegin(), topo.rend());
}

graph read();
void write(const std::vector<int> &t);

int main() {
  auto G = read();
  auto T = solve(G);
  write(T);

  return 0;
}

graph read() {
  std::ifstream fin("sortaret.in");
  int u, v, n, m;

  fin >> n >> m;

  graph G(n + 1, std::vector<int>());
  while (fin >> u >> v) {
    G[u].push_back(v);
  }

  return G;
}

void write(const std::vector<int> &T) {
  std::ofstream fout("sortaret.out");

  std::copy_n(T.begin(), T.size(), std::ostream_iterator<int>(fout, " "));
  fout << '\n';
}