Cod sursa(job #2666800)

Utilizator anamaria2602Avram Ana Maria anamaria2602 Data 2 noiembrie 2020 15:20:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
vector <int> M[100001];///Lista de muchii
vector <int> Sortare; ///Vectorul final sortat
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int Viz[100001], X1, X2;
int NrComponenteConexe, Dimensiune, N1, N2;
void Dfs(int x)
{
    Viz[x] = 1; ///vizitam nodul curent
    for ( int i = 0; i < M[x].size(); i ++ ) ///parcurgem vectorul de muchii al nodului
        if ( Viz[ M[x][i] ] == 0 ) ///daca am gasit o muchie care nu a fost vizitata
            Dfs ( M[x][i] ); ///apelam recursiv
    Sortare.push_back(x); ///adaugam nodul in vectorul sortat
}
int main()
{
    f >> N1 >> N2;
    for ( int i = 1; i <= N2; i++)
    {
        f >> X1 >> X2;  ///actualizam lista de adiacenta
        M[X1].push_back(X2);
    }
    for ( int i = 1; i <= N1; i++)
        if (Viz[i]==0) ///daca am gasit un nod nevizitat
            Dfs(i); ///il parcurgem in adancime
    Dimensiune = Sortare.size() - 1; ///aflam dimensiunea vectorului sortat
    for ( int i = Dimensiune; i >= 0; i-- ) ///afisam vectorul in urma sortarii topologice
        g << Sortare[i] << " ";

    return 0;
}