Cod sursa(job #2947982)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 26 noiembrie 2022 23:58:50
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
// Mihai Priboi

#include <stdio.h>
#include <vector>

using namespace std;

#define MAXN 50000

int n, m;
vector<int> v[MAXN + 1];
int viz[MAXN + 1], ord[MAXN], ordInd;

void dfs(int node) {
  viz[node] = true;

  for(auto next : v[node])
    if (!viz[next])
      dfs(next);
  
  ord[ordInd++] = node;
}

int main() {
  FILE *fin, *fout;
  int i, x, y;

  fin = fopen("sortaret.in", "r");

  fscanf(fin, "%d%d", &n, &m);
  for(i = 0; i < m; i++) {
    fscanf(fin, "%d%d", &x, &y);
    v[x].push_back(y);
  }

  fclose(fin);

  for(i = 1; i <= n; i++)
    if (!viz[i])
      dfs(i);

  fout = fopen("sortaret.out", "w");

  for(i = n - 1; i >= 0; i--)
    fprintf(fout, "%d ", ord[i]);

  fclose(fout);
  return 0;
}