Cod sursa(job #2468775)

Utilizator Leonard1998Olariu Leonard Leonard1998 Data 5 octombrie 2019 22:21:50
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
#include <vector>
#include <stack>

#define NMAX (int)(5e4 + 5)

using namespace std;

int n, m, x, y;
vector<int> g[NMAX];
int viz[NMAX];
stack<int> topological_order;

void DFS(int x) {
    viz[x] = 1;

    for (int y : g[x])
        if (!viz[y]) DFS(y);

    topological_order.push(x);
}

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

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

    for (int i = 1; i <= n; ++i)
        if (!viz[i]) DFS(i);

    while (!topological_order.empty()) {
        printf("%d ", topological_order.top());
        topological_order.pop();
    }
    printf("\n");

    return 0;
}