Cod sursa(job #797467)

Utilizator gallexdAlex Gabor gallexd Data 14 octombrie 2012 06:45:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <vector>
#include <list>
using namespace std;

#define LMAX 50010

int N, M;
vector<int> V[LMAX];
list<int> sol;
int inedges[LMAX];

void dfs(int nod) {
    int e=V[nod].size(), n;
    for (int i=0; i<e; ++i) {
        n = V[nod][i];
        --inedges[n];
        if (!inedges[n]) {
            --inedges[n];
            sol.push_back(n);
            dfs(n);
        }
    }
}

void topsort() {
    for (int i=1; i<=N; ++i)
        if (!inedges[i]) {
            sol.push_back(i);
            dfs(i);
        }
}

int main () {

    int x,y;

    freopen("sortaret.in","rt",stdin);
    freopen("sortaret.out","wt",stdout);

    scanf("%d %d", &N, &M);
    for (int i=0; i<M; ++i) {
        scanf("%d %d", &x, &y);
        V[x].push_back(y);
        ++inedges[y];
    }

    topsort();

    for (list<int>::iterator it=sol.begin(); it!=sol.end(); ++it)
        printf("%d ", *it);
    return 0;
}