Cod sursa(job #1403547)

Utilizator BLz0rDospra Cristian BLz0r Data 27 martie 2015 13:15:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <bitset>
#include <stack>
#include <vector>
using namespace std;

#define Nmax 50002
#define pb push_back

FILE *f = fopen ( "sortaret.in", "r" );
FILE *g = fopen ( "sortaret.out", "w" );

vector < int > G[Nmax];
bitset < Nmax > viz;
stack < int > sol;

void DFS ( int nod ){
    vector < int > :: iterator it;

    viz[nod] = 1;

    for ( it = G[nod].begin(); it < G[nod].end(); ++it )
        if ( !viz[*it] )
            DFS ( *it );

    sol.push ( nod );
}

int main(){
    int N, M, x, y;
    vector < int > :: iterator it;

    fscanf ( f, "%d%d", &N, &M );

    for ( int i = 1; i <= M; ++i ){
        fscanf ( f, "%d%d", &x, &y );
        G[x].pb ( y );
    }

    for ( int i = 1; i <= N; ++i )
        if ( !viz[i] )
            DFS ( i );

    while ( !sol.empty() ){
        fprintf ( g, "%d ", sol.top() );
        sol.pop();
    }

    return 0;
}