Cod sursa(job #1966148)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 14 aprilie 2017 22:14:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
#include <vector>

const int MAXN = 1e5;

std::vector <int> g[MAXN + 1];
bool r[MAXN + 1];
int ans[MAXN + 1];
int o;

void dfs(int u) {
  r[u] = 1;
  for (int i = 0; i < g[u].size(); ++i) {
    if (!r[g[u][i]]) {
      dfs(g[u][i]);
    }
  }
  ans[++o] = u;
}

int main() {
  int n, m, x, y;
  FILE *f = fopen("sortaret.in", "r");
  fscanf(f, "%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    fscanf(f, "%d%d", &x, &y);
    g[x].push_back(y);
  }
  fclose(f);
  for (int i = 1; i <= n; ++i) {
    if (!r[i]) {
      dfs(i);
    }
  }
  f = fopen("sortaret.out", "w");
  for (int i = n; i > 0; --i) {
    fprintf(f, "%d ", ans[i]);
  }
  fprintf(f, "\n");
  fclose(f);
  return 0;
}