Cod sursa(job #3164716)

Utilizator christalknightChristian Micea christalknight Data 4 noiembrie 2023 10:08:25
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int nmax = 50003;
int n, m;
bool viz[nmax];
bool tempMark[nmax];            //pt a determina daca exista sau nu ciclu in graf
vector <int> g[nmax];
stack <int> topologicOrder;

void dfs(int nod);
void read(void);

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

    while(!topologicOrder.empty()){
        fout<<topologicOrder.top()<<" ";
        topologicOrder.pop();
        }
    }

void read(void){
    int i, j;
    
    fin>>n>>m;

    while(m--){
        fin>>i>>j;
        g[i].push_back(j);
        }
    }

void dfs(int nod){
    int i, vecin;
    
    if(tempMark[nod]){
        cout<<"ERROR - cycle detected\n";
        return;
        }

    tempMark[nod] = true;

    for(i = 0; i < g[nod].size(); i++){
        vecin = g[nod][i];
        if(!viz[vecin])
            dfs(vecin);
        }

    tempMark[nod] = false;
    viz[nod] = true;
    topologicOrder.push(nod);
    }