Cod sursa(job #2952514)

Utilizator Theodor17Pirnog Theodor Ioan Theodor17 Data 9 decembrie 2022 14:55:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

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

const int NMAX = 1e5;

vector <int> g[NMAX + 1];
bitset <NMAX + 1> viz;
int comp_conexe;

void dfs(int x){

    viz[x] = 1;
    for(auto y : g[x])
        if(!viz[y])
            dfs(y);

}

int main(){

    int n = 0, m = 0;
    cin >> n >> m;

    for(int i = 0; i < m; i++){

        int x = 0, y = 0;
        cin >> x >> y;

        g[x].push_back(y);
        g[y].push_back(x);

    }

    for(int i = 1; i <= n; i++){
        if(!viz[i]){

            comp_conexe++;
            dfs(i);

        }
    }

    cout << comp_conexe;


    return 0;
}