Cod sursa(job #2241300)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 15 septembrie 2018 15:00:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <vector>
#include <stdio.h>

#define NMAX 50000

using namespace std;

vector <int> g [ NMAX + 1 ] ;
vector <int> v ;
int v2 [ NMAX + 1 ] ;
  FILE *fin, *fout ;


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

    for (i = 0 ; i < g[u].size() && v2[g[u][i]] == 1  ; i++ );

    if (i == g[u].size())
      v.push_back(u) ;
  }
}

int main() {

  fin = fopen ("sortaret.in", "r" ) ;
  fout = fopen ("sortaret.out", "w" ) ;
  int n, i, m, u, u2;
  fscanf (fin, "%d%d", &n, &m ) ;
  for (i = 0 ; i < m ; i++ ) {
    fscanf (fin, "%d%d", &u, &u2);
    g[u].push_back(u2) ;
  }
  for (i = 1 ; i <= n ; i++ )
    dfs (i) ;
  for (i = v.size()-1 ; i >= 0 ; i-- )
    fprintf (fout, "%d ", v[i] ) ;
  return 0;
}