Cod sursa(job #3266756)

Utilizator vladorovOroviceanu Vlad vladorov Data 10 ianuarie 2025 10:38:27
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int n;

vector<int> adj_list[50001];

int top_ord[50001];

bool viz[50001];

void dfs(int start, int& k){
    viz[start]=true;

    for(auto next : adj_list[start]){
        if(!viz[start]){
            dfs(next, k);
        }
    }

    top_ord[k++]=start;
}

void topsort(){
    int k=0;

    for(int i=1; i<=n; i++){
        if(!viz[i]){
            dfs(i, k);
        }
    }
}

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

    int m; fin>>n>>m;

    for(int i=0; i<m; i++){
        int x, y; fin>>x>>y;

        adj_list[x].push_back(y);
    }

    topsort();

    for(int i=0; i<n; i++){
        fout<<top_ord[i]<<" ";
    }

    return 0;
}