Cod sursa(job #1016683)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 26 octombrie 2013 16:40:47
Problema Sortare topologica Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int Nmax = 50005;
const int Mmax = 100005;

vector <int> G[Nmax];
char viz[Nmax], topsort[Nmax];
int N, M, TP;

inline int cmp( int x, int y )
{
    return x > y;
}

void read()
{
    freopen("sortaret.in", "r", stdin);

    scanf("%d %d", &N, &M);

    for ( int i = 1, a, b; i <= M; ++i )
    {
        scanf("%d %d", &a, &b);

        G[a].push_back( b );
    }

    for ( int i = 1; i <= N; ++i )
    {
        sort( G[i].begin(), G[i].end(), cmp );
    }
}

void DFS( int nod )
{
    viz[nod] = 1;

    for ( unsigned i = 0; i < G[nod].size(); ++i )
    {
        if ( !viz[ G[nod][i] ] )
                DFS( G[nod][i] );
    }

    topsort[ ++TP ] = nod;
}

void solve()
{
    freopen("sortaret.out", "w", stdout);

    for ( int i = N; i >= 1; --i )
            if ( !viz[i] )
                    DFS( i );

    for ( int i = TP; i >= 1; --i )
            printf("%d ", topsort[i]);

    printf("\n");
}

int main()
{
    read();
    solve();

    return 0;
}