Cod sursa(job #3136159)

Utilizator sebuxSebastian sebux Data 5 iunie 2023 16:06:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
#define optim ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define let auto
#define popcount __builtin_popcount
#define ctzll __builtin_ctzll
#define clzll __builtin_clzll

using namespace std;
string filename = "dfs";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");


const int sze = 1e5;
vector<int> G[sze + 1];
bitset<sze + 1> F;
int n, m;

void DFS(int x){
    F[x] = 1;
    for(let i : G[x]){
        if(!F[i]) DFS(i);
    }
}


int main()
{
    fin>>n>>m;
    int x, y;
    while(m--){
        fin>>x>>y;
        G[x].pb(y);
        G[y].pb(x);
    }
    int nr =0;
    for(int i = 1;i<=n;++i){
        if(!F[i]){
            nr++;
            DFS(i);
        }
    }
    fout<<nr;


    return 0;
}