Cod sursa(job #2382562)

Utilizator SemetgTemes George Semetg Data 18 martie 2019 14:36:00
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

const string FILE_NAME = "sortaret";
const int N_MAX = 50005;

int N;
vector<int> g[N_MAX];
vector<int> sol;
bool viz[N_MAX];

void init() {
    ifstream in { FILE_NAME + ".in" };
    
    int m;
    in >> N >> m;
    
    while (m--) {
        int x, y;
        in >> x >> y;
        
        g[x].emplace_back(y);
    }
}

void dfs(int node) {
    viz[node] = true;
    
    for (const auto& next : g[node])
        if (!viz[next])
            dfs(next);
    
    sol.emplace_back(node);
}

void solve() {
    for (int i = 1; i <= N; ++i)
        if (!viz[i])
            dfs(i);
}

void print() {
    ofstream out { FILE_NAME + ".out" };
    
    for (auto it = sol.rbegin(); it != sol.rend(); ++it)
        out << *it << ' ';
}

int main() {
    init();
    solve();
    print();
}