Cod sursa(job #1528980)

Utilizator MayuriMayuri Mayuri Data 20 noiembrie 2015 12:53:52
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <vector>

using namespace std;

vector <int> ts;
vector <int> G[50005];
vector <int> viz;

void topo_sort(int u) {
    int v, n = G[u].size();
    viz[u] = 1;
    for(int j = 0; j < n; ++ j) {
        v = G[u][j];
        if(!viz[v])
            topo_sort(v);
    }
    ts.push_back(u);
}

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

    int n, m, x, y, e;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; ++ i) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
    }
    viz.assign(n + 1, 0);

    for(int i = 1; i <= m; ++ i) {
        if(!viz[i])
            topo_sort(i);
    }

    e = ts.size();

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

    return 0;
}