Cod sursa(job #1735994)

Utilizator jurjstyleJurj Andrei jurjstyle Data 31 iulie 2016 20:16:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#include <list>

using namespace std ;

ifstream f ("sortaret.in") ;
ofstream g ("sortaret.out") ;

vector <int> G[50005] ; //memoreaza graful
list <int> sol ; //lista de varfuri solutie
vector <int> viz ; //memoreaza "gradul" de vizitare
int N , M ; //nr de noduri si muchii

void DFS ( int ) ;

int main ()
{
 f >> N >> M ; //citim
 viz.resize ( N + 1 ) ; //atribuim vectorului marimea "optima"
 for ( int i = 1  ; i <= M ; ++i )
    {
     int x , y ;
     f >> x >> y ; //citim muchia
     G[x].push_back ( y ) ; //o adaugam structurii
    }
 for ( int i = 1 ; i <= N ; ++i ) //parcurgem nodurile
    if ( viz[i] == 0 ) //daca nodul nu a mai fost parcurs
        DFS ( i ) ; //apelam dfs de el

 for ( list <int> :: iterator I = sol.begin () ; I != sol.end () ; ++I ) //afisam lista de noduri solutie
    g << *I << " " ;
}

void DFS ( int varf )
{
 viz[varf] = 1 ; //initial ii atribum varfului o valoare parcurs "partial"
 for ( vector <int> :: iterator I = G[varf].begin () ; I < G[varf].end () ; ++I ) //ii parcurgem vecinii
        if ( viz[*I] == 0 ) //daca n-a mai fost parcurs deloc
            DFS ( *I ) ; //apelam dfs de el
 viz[varf] = 2 ; //acum il marcam ca "parcurs de tot"
 sol.push_front ( varf ) ; //il adaugam la capatul stanga al listei
}