Cod sursa(job #2026151)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 23 septembrie 2017 19:43:42
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector <int> A[50001] ;
int n , m ;
bool vizitat[50001] ;
int nr = 0 ;
int postordine[50001] ;

void citire ()
{
    int x , y ;
    ifstream fin ("sortaret.in") ;
    fin >> n >> m ;
    for ( int i = 0 ; i < m ; i++ )
    {
        fin >> x >> y ;
        A[x].push_back(y) ;
    }
}

void DFS ( int nod )
{
    vizitat[nod] = true ;
    for ( int i = 0 ; i < A[nod].size() ; i++ )
    {
        if ( !vizitat[A[nod][i]] )
        {
            DFS(A[nod][i]) ;
        }
    }
    postordine[nr] = nod ;
    nr++ ;
}

int main()
{
    ofstream fout("sortaret.out") ;
    citire() ;
    for ( int i = 1 ; i <= n ; i++ )
        if ( !vizitat[i] )
            DFS(i) ;
    for ( int i = n - 1 ; i >= 0 ; i-- )
        fout << postordine[i] << " " ;
}