Cod sursa(job #3031804)

Utilizator SSKMFSS KMF SSKMF Data 20 martie 2023 20:10:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
using namespace std;

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

vector < vector <int> > adiacenta;

int noduri , muchii , vizitat[100001];

void Parcurgere (int nod)
{
    vizitat[nod] = 1;

    for (auto nod_vecin : adiacenta[nod])
        if (!vizitat[nod_vecin])
            Parcurgere(nod_vecin);
}

int main ()
{
    cin >> noduri >> muchii;
    adiacenta.resize(noduri + 1);

    int nod_1 , nod_2;
    for (int indice = 1 ; indice <= muchii ; indice++)
        cin >> nod_1 >> nod_2 , adiacenta[nod_1].push_back(nod_2) , adiacenta[nod_2].push_back(nod_1);

    int componente_conexe = 0;
    for (int nod = 1 ; nod <= noduri ; nod++)
        if (!vizitat[nod])
            Parcurgere(nod) , componente_conexe++;

    cout << componente_conexe;
    cout.close(); cin.close();
    return 0;
}