Cod sursa(job #3145816)

Utilizator not_anduAndu Scheusan not_andu Data 17 august 2023 10:45:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

#define INFILE "dfs.in"
#define OUTFILE "dfs.out"

// numarul de componente conexe

const int NMAX = 1e5 + 2;

vector<int> adj[NMAX];
bool viz[NMAX];

void dfs(int nod){

    viz[nod] = 1;

    for(int i = 0; i < adj[nod].size(); ++i){

        int to = adj[nod][i];

        if(!viz[to]){
            dfs(to);
        }
    }

}

void solve(){

    int n, m;

    cin >> n >> m;

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

        int x, y;

        cin >> x >> y;

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

    }

    int nrComp = 0;

    for(int nod = 1; nod <= n; ++nod){

        if(!viz[nod]){

            dfs(nod);

            ++nrComp;

        }

    }

    cout << nrComp << '\n';

}

int main(){
    
    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);
    cout.tie(nullptr);

    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);

    solve();

    return 0;
}