Cod sursa(job #1968117)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 17 aprilie 2017 14:54:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 5e4 + 10;

int n, m;
int used[nmax];
vector < int > g[nmax];

vector < int > topo;

void input() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y; scanf("%d %d", &x, &y);
        g[x].push_back(y);
    }
}

void dfs(int node) {
    used[node] = 1;
    for (auto &it: g[node]) {
        if (used[it]) continue;
        dfs(it);
    }

    topo.push_back(node);
}

void topo_sort() {
    for (int i = 1; i <= n; ++i)
        if (!used[i]) dfs(i);
    reverse(topo.begin(), topo.end());
}

void output() {
    for (auto &it: topo)
        printf("%d ", it);
    printf("\n");
}

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

    input();
    topo_sort();
    output();

    return 0;
}