Cod sursa(job #2488759)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 7 noiembrie 2019 16:39:34
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

const int MAX_N = 50005;

int n, m;

std::vector <int> top_sort;
std::vector <bool> visited(MAX_N);
std::vector <int> g[MAX_N];

void dfs(int u) {
  visited[u] = true;
  for (int v : g[u]) {
    if (visited[v] == 0) {
      dfs(v);
    }
  }
  top_sort.push_back(u);
}

int main() {
  int u, v;
  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w", stdout);
  scanf("%d %d", &n, &m);
  while (m --) {
    scanf("%d %d", &u, &v);
    g[u].push_back(v);
  }
  int p = 1;
  while (p <= n) {
    if (visited[p] == 0) {
      dfs(p);
    }
    ++p;
  }
  reverse(top_sort.begin(), top_sort.end());
  for (int v : top_sort) {
    printf("%d ", v);
  }
#ifdef LOCAL_DEFINE
  std::cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}