Cod sursa(job #2862744)

Utilizator NanuGrancea Alexandru Nanu Data 5 martie 2022 19:43:39
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

#define DIM 50000

bool sel[DIM + 1];
int n, m, x, y;
vector<int> G[DIM + 1];
stack <int> ST;

static inline void dfs(int nod) {
  sel[nod] = 1;
  for(auto e : G[nod])
    if(!sel[e])
      dfs(e);
  ST.push(nod);
}

static inline void TopSort() {
  for(int i = 1; i <= n; i++)
    if(!sel[i])
      dfs(i);
  while(!ST.empty()) {
    fout << ST.top() << " ";
    ST.pop();
  }
}

int main() {
  fin >> n >> m;
  for(int i = 1; i <= m; i++) {
    fin >> x >> y;
    G[x].push_back(y);
  }

  TopSort();

  return 0;
}