Cod sursa(job #3293991)

Utilizator sasha30ro@gmail.comManea Alexia Ioana [email protected] Data 14 aprilie 2025 17:47:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

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

// g[i] = lista de vecini a nodului i
vector<int> g[100005];

// viz[i] = true daca nodul i a fost deja vizitat
bool viz[100005];

int n, m; // n = numar de noduri, m = numar de muchii

// Functie DFS care viziteaza toate nodurile conectate cu 'nod'
void dfs(int nod)
{
    viz[nod] = true; // Marcam nodul ca vizitat

    // Parcurgem toti vecinii nodului curent
    for (auto vec : g[nod])
        if (!viz[vec])       
            dfs(vec); 
}

int main()
{
    f >> n >> m;

    // Citim cele m muchii si construim graful 
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        g[x].push_back(y); // Adaugam y in lista de vecini a lui x
        g[y].push_back(x); // Adaugam x in lista de vecini a lui y 
    }

    int cnx = 0; // Numarul de componente conexe

    // Parcurgem toate nodurile
    for (int i = 1; i <= n; i++)
        if (!viz[i])         // Daca nodul nu a fost vizitat
        {
            dfs(i);          // Pornim un DFS din acel nod
            cnx++;           // Am gasit o noua componenta conexa
        }

    gg << cnx; // Afisam numarul total de componente conexe
    return 0;
}