Cod sursa(job #3319720)

Utilizator riaNoLRian Oren riaNoL Data 2 noiembrie 2025 20:35:55
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector<int> viz(50000,0);
vector<int> L[50000];
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;
    fin >> nr_n >> nr_m;

    for (int i = 1 ;i<=nr_m; i++) {
        fin >> 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--)
        fout << order[i] << " ";
}