Cod sursa(job #2241297)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 15 septembrie 2018 14:52:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 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) ;
  //  for ( i = 0 ; i < v.size() ; i++ )
    //  fprintf (fout, "%d ", v[i] ) ;
   // fprintf (fout, "\n" ) ;
  }
}

int main() {

  fin = fopen ("sortaret.in", "r" ) ;
  fout = fopen ("sortaret.out", "w" ) ;
  int n, i, m, u, u2, j;
  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 ++ ) {
    //for (j = 0 ; j < g[i].size() ; j++ )
    //  fprintf (fout, "%d ", g[i][j] ) ;
    //fprintf (fout, "\n" ) ;
 // }
  for (i = 1 ; i <= n ; i++ )
    dfs (i) ;
  for (i = v.size()-1 ; i >= 0 ; i-- )
    fprintf (fout, "%d ", v[i] ) ;
  return 0;
}