Cod sursa(job #2724690)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 17 martie 2021 17:49:45
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <stack>
#include <vector>
#include <bitset>

auto *in = fopen("sortaret.in", "r") ;
auto *out = fopen("sortaret.out", "w") ;

const int maxn = 5e4 ;

std::vector<int> G[1 + maxn] ;
std::stack<int> sol ;
std::bitset<1 + maxn> seen ;

void dfs(int node) {
    seen[node] = 1;
    for (auto it : G[node]) {
        if (!seen[it]) {
            dfs(it) ;
        }
    }
    sol.push(node) ;
}

int main() {
    int n, m, x, y ;
    fscanf(in, "%d %d", &n, &m) ;
    for (int i = 1 ; i <= m ; ++ i) {
        fscanf(in, "%d %d", &x, &y) ;
        G[x].push_back(y) ;
    }
    for (int i = 1 ; i <= n ; ++ i) {
        if (!seen[i]) {
            dfs(i) ;
        }
    }
    while (!sol.empty()) {
        fprintf(out, "%d ", sol.top()) ;
        sol.pop() ;
    }
}