Cod sursa(job #2670641)

Utilizator HumikoPostu Alexandru Humiko Data 10 noiembrie 2020 13:19:48
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
///Alex Postu
 
#include <bits/stdc++.h>
 
using namespace std;

static const int NMAX = 5e4+5;
static const int MMAX = 1e5+5;

int f[NMAX];
vector <int> graph[NMAX];
stack <int> sortedVertices;

void dfs(int vertex) {
  f[vertex] = 1;
  for ( auto x:graph[vertex] ) {
    if (!f[x]) {
      dfs(x);
    }
  }

  sortedVertices.push(vertex);
}

void topologicalSort(int n, int m) {
  for ( int i = 1; i <= n; ++i ) {
    if ( !f[i] ) {
      dfs(i);
    }
  }
}

 
 int main() {
  #ifdef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
  #else
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
  #endif
 
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  int n, m = 0;

  cin>>n>>m;

  for ( int i = 1; i <= m; ++i ) {
    int x, y;
    cin>>x>>y;
    graph[x].push_back(y);
  }

  topologicalSort(n, m);

  while (!sortedVertices.empty()) {
    cout<<sortedVertices.top()<<" ";
    sortedVertices.pop();
  }
}