Cod sursa(job #874522)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 8 februarie 2013 18:32:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <vector>
#include <deque>
#include <cstdio>

using namespace std;

#define maxN 50005
#define PB push_back

vector <int> G[maxN];
deque <int> Q;
bool viz[maxN];

void DFS (int root)
{
    viz[root] = true;

    for (unsigned int i = 0 ; i < G[root].size() ; ++i)
    {
        int node = G[root][i];

        if (viz[node])
            continue;

        DFS (node);
    }

    Q.push_back(root);
}

int main()
{
    freopen ("sortaret.in" , "r" , stdin);
    freopen ("sortaret.out" , "w" , stdout);

    int N , M , A , B;

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

    while (M --)
    {
        scanf ("%d %d" , &A , &B);

        G[A].PB(B);
    }

    for (int i = 1 ; i <= N ; ++i)
    {
        if (viz[i])
            continue;

        DFS (i);
    }

    while (!Q.empty())
    {
        printf ("%d " , Q.back());
        Q.pop_back();
    }

    return 0;
}