Cod sursa(job #3266762)

Utilizator vladorovOroviceanu Vlad vladorov Data 10 ianuarie 2025 10:46:04
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int n;

vector<int> adj[100001];

int top_ord[100001];
bool viz[100001];

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

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

    top_ord[k--]=start;
}

void topsort(){
    int k=n-1;

    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[x].push_back(y);
    }

    topsort();

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

    return 0;
}