Cod sursa(job #3004998)

Utilizator VenomPool9Bogdan VenomPool9 Data 16 martie 2023 18:43:32
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50'001;
int n, m; // nodes and edges 
vector<int> adj[NMAX];
vector<int> topological;
bool visited[NMAX];

void read(){
    fin >> n >> m;
    for(int i = 0; i < m; ++i){
        int a,b;
        fin >> a >> b;
        adj[a].push_back(b);
    }
}

void dfs(int u){
    visited[u] = true;
    for(auto v : adj[u])
        if(!visited[v])
            dfs(v);
    topological.push_back(u);
}

void topSort(){
    for(int i = 1; i <= n; ++i)
        if(!visited[i])
            dfs(i);
    reverse(topological.begin(), topological.end());
    for(auto it : topological)
        fout << it << ' ';
}

int main(){
    read();
    topSort();
    return 0;
}