Cod sursa(job #2423864)

Utilizator livliviLivia Magureanu livlivi Data 22 mai 2019 00:55:10
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

vector<vector<int>> edge;
vector<bool> viz;
stack<int> ans;

void dfs(int node){
    viz[node] = true;
    
    for(auto now : edge[node])
        if (viz[now] == false)
            dfs(now);
            
    ans.push(node);
}

int main(){
    ifstream cin ("sortaret.in");
    ofstream cout ("sortaret.out");
    
    int n, m; cin >> n >> m;
    edge.resize(n);
    viz.resize(n, false);
    
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        edge[a - 1].push_back(b - 1);
    }
    
    for(int i = 0; i < n; i++)
        if (viz[i] == false)
            dfs(i);
            
    while(!ans.empty()){
        cout << ans.top() + 1 << ' ';
        ans.pop();
    }
    
    cout << '\n';
    return 0;
}