Cod sursa(job #3223187)

Utilizator calin123456789Calin Rusanu calin123456789 Data 12 aprilie 2024 16:49:31
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> g;

int n, m, vis[100001], a, b, cnt;

void DFS(int node){
    vis[node]=true;
    for(int i=0; i<g[node].size(); i++){
        int vec = g[node][i];
        if(vis[vec]==0){
            DFS(vec);
        }
    }
}

int main()
{
    cin>>n>>m;
    g.resize(n+1);
    for(int i=1; i<=m; i++){
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int node=1; node<=n; node++){
        if(!vis[node]){
            cnt++;
            DFS(node);
        }
    }
    cout<<cnt;
    return 0;
}