Cod sursa(job #2594660)

Utilizator RazorBestPricop Razvan Marius RazorBest Data 6 aprilie 2020 15:00:01
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda laborator_7_sd_313cab Marime 0.79 kb
#include <cstdio>
#include <vector>
#include <stack>
#define NMAX 100000

std::vector<int> adj[NMAX + 1];
char visited[NMAX + 1];
std::stack<int> s;

void dfs(int node) {
    visited[node] = 1;
    
    for (auto it = adj[node].begin(); it != adj[node].end(); it++) {
        if (!visited[*it]) {
            dfs(*it);
        }
    }
    s.push(node);
}

int main() {
    int n, m, x, y;
    int gr[NMAX + 1] = {0};
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        gr[y]++;
    }

    for (int i = 1; i <= n; i++) {
        if (gr[i] == 0) {
            dfs(i);
        }
    }

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