Cod sursa(job #1334891)

Utilizator gallexdAlex Gabor gallexd Data 4 februarie 2015 19:13:29
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <vector>

using namespace std;

int N, M;
vector<int> V[50010];
vector<int> S;
bool viz[50010];
int x, y;

void dfs(int n) {
    for (int i=0; i<V[n].size(); ++i) {
        if (!viz[V[n][i]]) {
            viz[V[n][i]] = true;
            dfs(V[n][i]);
        }
    }

    S.push_back(n);
}

void sortare() {
    for (int i=1; i<=N; ++i) {
        if (!viz[i]) {
            dfs(i);
            //S.push_back(i);
        }
    }
}

int main () {


    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);
    }

    sortare();

    for (int i=S.size()-1; i>=0; --i) {
        printf("%d ", S[i]);
    }

    return 0;
}