Cod sursa(job #2428152)

Utilizator Mr.DoomRaul Ignatus Mr.Doom Data 4 iunie 2019 00:45:07
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;


int n, m;
vector<vector<int>> G;
vector<bool> v;
stack<int> s;

void Read();
void DF(int x);

void Write();

int main() {
    Read();
    for (int i = 1; i <= n; ++i)
        if (!v[i])
            DF(i);
    Write();
    return 0;
}


void Read() {
    ifstream is("sortaret.in");
    
    is >> n >> m;
    G = vector<vector<int>>(n + 1);
    v = vector<bool>(n + 1);
    int x, y;
    for (int i = 0; i < m; ++i) {
        is >> x >> y;
        G[x].push_back(y);
    }
    
    is.close();
}

void DF(int x) {
    v[x] = true;
    for (const auto& y : G[x])
        if (!v[y])
            DF(y);
            
    s.push(x);
}

void Write() {
    ofstream os("sortaret.out");
    while (!s.empty()) {
        os << s.top() << ' ';
        s.pop();
    }
    os.close();
}