Cod sursa(job #2795685)

Utilizator Marie02THGStanescu Maria Raluca Marie02THG Data 6 noiembrie 2021 19:39:09
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

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

#define Nmax 50005


vector<int> la[Nmax];  ///lista de adiacenta
vector<int> vizitat(Nmax,0); ///v de viz
vector<int> stiva;

void sortaret(int x)
{
    vizitat[x]=1;  ///marcam nodul curent ca vizitat
    for(int nod : la[x])
    {
        if(vizitat[nod]==0) ///daca dam in lista de adiacenta peste un nod nevizitat facem dfs
            sortaret(nod);
    }
    stiva.push_back(x); ///dupa ce parcurgem lista de adiacenta punem nodul curent in stiva
}

int main()
{
    int N,M;
    in>>N>>M; ///nr noduri + nr muchii
    for(int i=1 ; i <= M ; i++)
    {
        int a,b;
        in>>a>>b;
        la[a].push_back(b);
    }
    for(int i=1; i<=N; i++)
    {
        if(vizitat[i]==0)
            sortaret(i); ///pt fiecare nod nevizitat apelam sortaret
    }
    for( int i=stiva.size() -1; i>=0; i--)  ///avand stiva , o parcurgem invers pt a afisa sortarea top.
        out<<stiva[i]<<" ";
    return 0;
}