Cod sursa(job #2238910)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 8 septembrie 2018 13:23:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <vector>

using namespace std;

const int N = 50000 + 5;

int n, m, st[N], cnt;

bool viz[N];

vector <int> g[N];

void dfs (int nod) {
  viz[nod] = 1;
  for (auto nou: g[nod]) {
    if (viz[nou] == 0) {
        dfs(nou);
    }
  }
  st[++cnt] = nod;
}

int main() {
  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w", stdout);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    g[a].push_back(b);
  }
  for (int i = 1; i <= n; i++) {
    if (viz[i] == 0) {
      dfs(i);
    }
  }
  for(int i = n; i >= 1; i--) {
    printf("%d ", st[i]);
  }
  printf("\n");
  return 0;
}