Pagini recente » Cod sursa (job #2649927) | Cod sursa (job #3206889) | Cod sursa (job #1427895) | Cod sursa (job #1530477) | Cod sursa (job #1735994)
#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
}