Cod sursa(job #2918836)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 13 august 2022 14:10:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

const int MAX_N = 100005;
int n, m, x, y, conex;
vector <int> edge[MAX_N];

bitset <MAX_N> viz;
void dfs(int nod){
    viz[nod] = true;
    for(auto vecin : edge[nod])
        if(!viz[vecin])
            dfs(vecin);
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n>>m;
    for(int e=1; e<=m; e++){
        fin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

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

    fout<<conex;
    return 0;
}