Cod sursa(job #1113387)

Utilizator techLaurentiu Avasiloaie tech Data 20 februarie 2014 16:11:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
#define MAX 50005

using namespace std;

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

std::vector<int> vect[MAX] ;
std::vector<int> sorted ;

int n , m , i , x , y , check[MAX] ;

void DFS ( int i )
{
    for ( std::vector<int>::iterator it = vect[i].begin() ; it != vect[i].end() ; ++ it )
    {
        if ( check[*it] == 0 )
        {
            DFS(*it) ;
        }
    }

    check[i] = 1 ;

    sorted.push_back(i) ;
}

void sorting ()
{
    for ( int i = 1 ; i <= n ; i ++ )
    {
        if ( check[i] == 0 )
        {
            DFS(i) ;
        }
    }
}

int main()
{
    in >> n >> m ;

    for ( i = 1 ; i <= m ; i ++ )
    {
        in >> x >> y ;
        vect[x].push_back(y) ;
    }

    sorting() ;

    for ( std::vector<int>::iterator it = sorted.end() - 1 ; it != sorted.begin() - 1 ; it -- )
    {
        out << *it << " " ;
    }

    return 0;
}