Cod sursa(job #2796086)

Utilizator popaandaioanaPopa Anda-Ioana popaandaioana Data 7 noiembrie 2021 15:55:07
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;

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

class graf_orientat
{
    int n, m; //n = nr. varfuri m = nr. arce
public:
    vector <int> lista[50001]; //in acest mod va fi stocat graful (lista adiacenta)
    bool vect[50001];
    graf_orientat(int, int); //constructor
    void construire_graf_orientat();
    void sortaret(int);
};

graf_orientat :: graf_orientat(int n, int m)
{
    this -> n = n;
    this -> m = m;
}

void graf_orientat :: construire_graf_orientat()
{
    for(int i = 0; i < m; i ++) //parcurgem arcele
    {
        int u, v;
        in >> u >> v; //citim varfurile intre care exista arc
        lista[v].push_back(u); //adaugam in lista de adiacenta
    }
}

void graf_orientat :: sortaret(int nod)
{
    vect[nod] = 1; //marcheaza cu 1 nodul (a fost viz.)
    for(int j : lista[nod]) //parcurge recursiv lista de adiacenta a nodului curent
        if(!vect[j]) //pentru vecinii neviz. ai lui nod
            sortaret(j); //face apel recursiv
    out << nod << " ";
}

int main()
{
    int n, m;
    in >> n >> m; //se citesc nr. de noduri, nr. de muchii
    graf_orientat G(n, m); //se apeleaza constructorul
    G.construire_graf_orientat(); //se apeleaza functia de construire a grafului
    //SORTARET

    for(int i = 1; i <= n; i ++) //parcurgem nodurile grafului
        if(!G.vect[i]) //daca in vect pe pozitia i avem 0 (nodul nu a fost viz.), apelam functia sortaret cu parametrul i
            G.sortaret(i);
    return 0;

}