Cod sursa(job #3317256)

Utilizator AlexDianaAlexandrescu Diana AlexDiana Data 22 octombrie 2025 22:04:41
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector<int>vizitat;    //0=nevizitat, 1=vizitat
vector<int> comp_curenta;    //nodurile din comp curenta

void dfs(int nod_curent, const vector<vector<int>>&l)
{
    vizitat[nod_curent] = 1;
    comp_curenta.push_back(nod_curent);     //adaug nod nou la comp cur
    for (int v : l[nod_curent])    //vecinii (daca nu l am viz, apelez dfs din el)
        if (vizitat[v] == 0)
            dfs(v, l);
}

int main() {
    int N, M, x, y;
    in >> N >> M;
    vector<vector<int>> l(N+1);
    vizitat.assign(N+1, 0);
    for(int i = 0; i < M; i++)
    {
        in >> x >> y;
        l[x].push_back(y);
    }

    // 4. Executia DFS si determinarea Componentelor Conexe
    int nr_comp = 0;

//    out << "Componente conexe \n";
    for (int i = 1; i <= N; i++)
    {
        if (vizitat[i] == 0)    //nu e vizitat deci am comp conexa noua
        {
            nr_comp++;
            comp_curenta.clear();     //incep noua comp
            dfs(i, l);
//            out << "Componenta " << nr_comp << " ";
//            for (int nod : comp_curenta)
//                out<< nod << " ";
//            out << "\n";
        }
    }
    out << nr_comp;

    return 0;
}