Cod sursa(job #1423700)

Utilizator CalinCojoFMI Cojocaru Calin George CalinCojo Data 22 aprilie 2015 13:02:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

vector <unsigned int > visited ;
vector <unsigned int > start_points ;
vector < vector <unsigned int > > adj_list;
vector < unsigned int > sol;

void sort_t ( unsigned int  x) {


    unsigned int i, head;
    bool Fnode ;
    stack <unsigned int > stiva ;
    stiva.push ( x );

    while ( !stiva.empty() ){

        Fnode = 0;
        head = stiva.top();
        visited [ head ] = 1 ;

        for ( i = 0 ; i < adj_list [ head ].size() ;  i++)
            if ( visited [ adj_list [ head ] [ i ]  ]  == 0 ){

                stiva.push (  adj_list [ head ] [ i ]  ) ;
                Fnode = 1;
                break;

            }

        if(!Fnode){
            sol.push_back( head );
            stiva.pop();
        }

    }
}

int main()
{
    int n , m , x , y;
    ifstream f( "sortaret.in" , ios::in );
    ofstream g ("sortaret.out", ios::out );
    f>>n>>m ;
    visited.resize ( n + 1 );
    fill ( visited.begin() , visited.end() , 0) ;
    start_points.resize ( n + 1);
    fill ( start_points.begin() , start_points.end() , 1);
    adj_list.resize( n+ 1);


    while(m){
        m--;
        f>>x>>y;
        adj_list [ x ].push_back ( y );
        start_points [ y ] = 0 ;
    }

    for( x = 1 ; x <= n ; x++)
        if( start_points [ x ])
            sort_t ( x );

    for( x = n-1; x >=0 ; x-- )
        g<<sol [ x ]<< "  ";

    return 0;
}