Cod sursa(job #3198025)

Utilizator satzaFoldesi Richard satza Data 28 ianuarie 2024 09:32:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
///topological sort based on dfs
///perform a dfs, store the fiinishing time for every vertex
///solution = the vertices in the reverse order of finishing time
#include <bits/stdc++.h>

using namespace std;

int N, M, nr;
vector<int>L[50002];///adjacency list
int vis[50002], topoSort[50002];
ifstream in("sortaret.in");
ofstream out("sortaret.out");

void dfs(int k){
    vis[k] = 1; ///grey
    for(int i = 0; i < L[k].size(); i++){
        int j = L[k][i];
        if(vis[j] == 0) dfs(j);
    }
    vis[k] = 2;///black
    topoSort[nr] = k;///reverse order
    nr = nr - 1;
}

int main(){
    in >> N >> M;
    nr = N;
    for(int i = 1; i <= M; i++){
        int x, y;
        in >> x >> y;
        L[x].push_back(y);
    }

    for(int i = 1; i <= N; i++)
        if(vis[i] == 0) dfs(i); ///if i is white perform a dfs starting with i

    for(int i = 1; i <= N; i++) out << topoSort[i] << " ";
    return 0;
}