Cod sursa(job #2841193)

Utilizator sanzianagrecuSanziana Grecu sanzianagrecu Data 29 ianuarie 2022 13:07:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;

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

#define NMAX 100001

vector <int> adia[NMAX];
int vizitat[NMAX], n, m;

void Dfs(int nod) {

    vizitat[nod] = 1;

    for (auto vecin : adia[nod])
        if (!vizitat[vecin])
            Dfs(vecin);

}

int main() {

    fin >> n >> m;
    for (int a, b, i = 1; i <= m; ++ i) {
        fin >> a >> b;
        adia[a].push_back(b);
        adia[b].push_back(a);
    }

    int nrComponente = 0;
    for (int i = 1; i <= n; ++ i) {
        if (!vizitat[i]) {
            nrComponente ++;
            Dfs(i);
        }
    }

    fout << nrComponente;

    fin.close();
    fout.close();
    return 0;
}