Cod sursa(job #2943063)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 20 noiembrie 2022 15:51:50
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

const int nmax = 5 * 1e4;
vector <int> graf[nmax + 1];
vector <int> sol;

bool marked[nmax + 1];
void dfs (int node){
  marked[node] = true;
  for ( auto neighbour : graf[node])
    if (!marked[neighbour]) dfs(neighbour);
  sol.push_back (node);
}

int main(){

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

  int n, m;
  fin >> n >> m;

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

  for (int i = 1; i <= n; i++)
    if (!marked[i])
      dfs(i);

  reverse(sol.begin(), sol.end());
  for (auto solutie : sol)
    fout << solutie << " ";
  return 0;
}