Cod sursa(job #2915869)

Utilizator db_123Balaban David db_123 Data 25 iulie 2022 15:46:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>

using namespace std;

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

int n,m;
vector<vector<int>> ma;
vector<bool> visited;

void read() {
    cin>>n>>m;
    ma.resize(n+1);
    visited.resize(n+1);
}

void dfs(int &node) {
    if(visited[node]) {
        return;
    }
    visited[node]=1;
    for(auto i:ma[node]) {
        dfs(i);
    }
}

void solve() {
    int a,b;
    for(int i=1;i<=m;i++) {
        cin>>a>>b;
        ma[a].push_back(b);
        ma[b].push_back(a);
    }
    int cnt=0;
    for(int i=1;i<=n;i++) {
        if(!visited[i]) {
            cnt++;
            dfs(i);
        }
    }
    cout<<cnt;
}

int main() {
    
    read();
    solve();
    return 0;
}