Cod sursa(job #3226622)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 22 aprilie 2024 12:13:23
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <vector>

using namespace std;

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

int const NMAX = 50000;
bool isVisit[1 + NMAX];
vector <int> g[1 + NMAX];

int ind = 0;
int ans[1 + NMAX];

void DFS(int node) {
  isVisit[node] = true;
  for(int i = 0;i < g[node].size();i++) {
    int to = g[node][i];
    if(!isVisit[to]) {
      DFS(to);
    }
  }
  ind++;
  ans[ind] = node;
}

int main() {

  int n, m;
  in >> n >> m;
  for(int i = 1;i <= m;i++) {
    int a, b;
    in >> a >> b;
    g[a].push_back(b);
  }
  for(int i = 1;i <= n;i++) {
    if(isVisit[i] == false) {
      DFS(i);
    }
  }
  for(int i = n;i >= 1;i--) {
    out << ans[i] << ' ';
  }
  return 0;
}