Cod sursa(job #1868094)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 4 februarie 2017 16:06:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>
#include <vector>

using namespace std;

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

void topo_sort(int u) {
    viz[u] = 1;
    int v;
    for(int i = 0; i < G[u].size(); ++ i) {
        v = G[u][i];
        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, u, v;

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; ++ i) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }

    viz.assign(n + 1, 0);
    for(int i = 1; i <= n; ++ i) {
        if(!viz[i]) {
            topo_sort(i);
        }
    }

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

    return 0;
}