Cod sursa(job #3319719)

Utilizator riaNoLRian Oren riaNoL Data 2 noiembrie 2025 20:33:39
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <vector>
using namespace std;


vector<int> viz(1000001,0);
vector<int> L[1000001];
vector <int> order;


bool DFS(int node) {
    //daca nodul in care suntem a fost deja vizitat inseamna ca exista un ciclu
    if (viz[node] == 1)
        return false;
    //daca nodul pe care il vizitam deja a fost vizitat inseamna ca nu a fost niciun ciclu si il putem adauga la order
    if (viz[node] == 2)
        return true;

    //Suntem in nodul curent deci VISITING it:
    viz[node] = 1;

    //Verificam daca pentru fiecare vecin daca exista un ciclu
    for (int vecin: L[node]) {
        if (!DFS(vecin))
            return false;
    }

    //Daca n-a existat nicio problema atunci am vizitat nodul cum trebuie
    viz[node] = 2;

    order.push_back(node);
    return true;
}

int main() {
    int nr_n, nr_m, nx, ny;
    cin >> nr_n >> nr_m;

    //Graf orientat
    for (int i = 1 ;i<=nr_m; i++) {
        cin >> nx >> ny;
        L[nx].push_back(ny);
    }
    for (int node = 1; node<=nr_n;node++) {
        if (!DFS(node))
            return -1;
    }

    for (int i = (int)order.size()-1; i>=0; i--)
        cout << order[i] << " ";
}