Cod sursa(job #2481052)

Utilizator Robert_VRVRobert Vadastreanu Robert_VRV Data 26 octombrie 2019 13:20:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <queue>
#include <stdio.h>
#include <vector>

const int MAX_N = 50000;

std::vector<int> G[5 + MAX_N];

int deg[5 + MAX_N];

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]++;
  }
  std::vector<int> ans;
  for (int i = 1; i <= n; i++)
    if (deg[i] == 0)
      ans.push_back(i);
  for (int i = 0; i < n; i++) {
    int node = ans[i];
    for (int v : G[node]) {
      deg[v]--;
      if (deg[v] == 0)
        ans.push_back(v);
    }
  }
  for (int i : ans)
    printf("%d ", i);
  printf("\n");

  return 0;
}