Cod sursa(job #3255316)

Utilizator uncle_sam_007ioan bulik uncle_sam_007 Data 10 noiembrie 2024 12:12:48
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int NMAX = 50005;

vector <int> g[NMAX], sol;
stack <int> st;
int n;
int viz[NMAX];

void DFS(int node){
    viz[node] = 1;
    for(auto edge:g[node]){
        if(!viz[edge]){
            DFS(edge);
        }
    }
    st.push(node);
}

void SortareTopologica(){
    for(int i = 1; i <= n; ++i){
        if(!viz[i]){
            DFS(i);
        }
    }
    while(!st.empty()){
        sol.push_back(st.top());
        st.pop();
    }
    for(auto ind:sol){
        fout << ind << " ";
    }
}

int main()
{
    int m, x, y;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        fin >> x >> y;
        g[x].push_back(y);
    }
    SortareTopologica();
    return 0;
}