Cod sursa(job #2279065)

Utilizator palomaPaloma Josse paloma Data 8 noiembrie 2018 21:07:31
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fi("sortaret.in");
ofstream fo("sortaret.out");

const int maxn = 50000;

vector <int> g[maxn + 1];

int k, n, m, q[maxn + 1];
bool vis[maxn + 1];

void dfs(int node) {
  vis[ node ] = 1;
  for (auto son: g[ node ]) {
    if (!vis[ son ])
      dfs(son);
  }
  q[ ++k ] = node;
}

int main()
{
  int x, y;

  fi >> n >> m;
  for (int i = 1; i <= m; i++) {
    fi >> x >> y;
    g[ x ].push_back(y);
  }

  for (int i = 1; i <= n; i++) {
    if (!vis[ i ])
      dfs( i );
  }

  for (int i = n; i >= 1; i--) {
    fo << q[ i ] << ' ';
  }

  fi.close();
  fo.close();

  return 0;
}