Cod sursa(job #2667455)

Utilizator Madalina.ZoicanZoican Alexandra-Madalina Madalina.Zoican Data 3 noiembrie 2020 14:45:18
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
vector <int> m[100001];///Lista de muchii
vector <int> st; ///Vectorul final sortat
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int vizitat[100001],N, M;
void DFS(int x)
{
    vizitat[x] = 1; ///vizitam nodul curent
    for ( int i = 0; i < m[x].size(); i ++ ) ///parcurgem vectorul de muchii al nodului
        if ( m[x][i] == 0 ) ///daca am gasit o muchie care nu a fost vizitata
            DFS ( m[x][i] ); ///apelam recursiv
    st.push_back(x); ///adaugam nodul in vectorul sortat
}
void read()
{
    fin >> N >> M;
    for ( int i = 1; i <= M; i++)
    {
        int x,y;
        fin >> x >> y;  ///actualizam lista de adiacenta
        m[x].push_back(y);
    }
    for ( int i = 1; i <= N; i++)
        if (vizitat[i]==0) ///daca am gasit un nod nevizitat
            DFS(i); ///il parcurgem in adancime
    for ( int i = st.size()-1; i >= 0; i-- ) ///afisam vectorul in urma sortarii topologice
        fout<< st[i] << " ";

}
int main()
{
    read();
    return 0;
}