Cod sursa(job #2438373)

Utilizator vladisimovlad coneschi vladisimo Data 12 iulie 2019 13:11:31
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <vector>

std::vector<int> G[2 + 50000];

int deg[2 + 50000], sol[2 + 50000];

int main() {
  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w", stdout);
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    deg[v]++;
  }
  for (int i = 1; i <= n; i++)
    if (deg[i] == 0) {
      sol[0]++;
      sol[sol[0]] = i;
    }
  for (int i = 1; i <= n; i++) {
    int u = sol[i];
    for (int v : G[u]) {
      deg[v]--;
      if (deg[v] == 0) {
        sol[0]++;
        sol[sol[0]] = v;
      }
    }
  }
  for (int i = 1; i <= n; i++)
    printf("%d ", sol[i]);
  return 0;
}