Cod sursa(job #3138982)

Utilizator NightCrawler92Alexandru Stefanica NightCrawler92 Data 23 iunie 2023 20:07:29
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>
#include <stack>


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

void dfs(Graph& g, std::stack<int>& s, int node) {
   g[0][node - 1] = 1;
   if (g[node].empty()) {
       s.push(node);
       return ;
   }
   for(const auto& x: g[node]) {
      if (!g[0][x - 1]) {
        dfs(g, s, x);
      }
   }
   s.push(node);
}

int main() {
  std::ifstream in{ "sortaret.in" };

  int N, M;
  Graph g;
  
  in >> N >> M;
  g.reserve(N + 1);
  for (int i = 0; i < M; ++i) {
    int x, y;
    in >> x >>  y;
    g[x].emplace_back(y);
  }
  g[0] = std::vector<int>(N, 0);

  std::stack<int> s;
  for (int i = 0; i < N; ++i) {
    if (!g[0][i]) {
      dfs(g, s, i + 1);
    }
  }

  std::ofstream out{"sortaret.out"};

  for(; !s.empty(); s.pop()) {
    out << s.top() << ' ';
  }

  return 0; 
}