Cod sursa(job #3145249)

Utilizator YusyBossFares Yusuf YusyBoss Data 14 august 2023 12:33:15
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
#define NMAX 50000

using namespace std;

vector <int> vsons[NMAX + 1];
bool is_visited[NMAX + 1];
int vsol[NMAX + 1], nsol;

void dfs(int node) {
  int i, nsons;

  is_visited[node] = 1;

  nsons = vsons[node].size();
  for (i = 0; i < nsons; i++) {
    int newnode = vsons[node][i];

    if (!is_visited[newnode])
      dfs(newnode);
  }

  vsol[nsol++] = node;
}

int main() {
  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w", stdout);

  int n, m, x, y, node, i;
  cin >> n >> m;

  for (i = 0; i < m; i++) {
    cin >> x >> y;
    vsons[x].push_back(y);
  }

  for (node = 1; node <= n; node++) {
    if (!is_visited[node])
      dfs(node);
  }

  for (i = nsol - 1; i >= 0; i--)
    cout << vsol[i] << " ";
  return 0;
}