Cod sursa(job #2850921)

Utilizator handicapatucavasi eduard handicapatu Data 17 februarie 2022 19:37:07
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
///Sortarea topologica este o ordonare a varfurilor unui graf astfel incat daca exista arc de la x inspre y , x vine inaintea lui y
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int n , m , x , y;
vector < int > G[50001];
stack < int > ans;
bool visited[50001];

void dfs(int x){
    visited[x] = true;
    for(int i = 0 ; i < G[x].size() ; ++i)
        if(!visited[G[x][i]])
            dfs(G[x][i]);
    ans.push(x);
}

int main(){
    f >> n >> m;
    for(int i = 1 ; i <= m ; ++i){
        f >> x >> y;
        G[x].push_back(y);
    }
    for(int i = 1 ; i <= n ; ++i)
        if(!visited[i])
            dfs(i);
    while(!ans.empty()){
        g << ans.top() << " ";
        ans.pop();
    }
    return 0;
}