Cod sursa(job #2672877)

Utilizator CRaresCroicia Rares CRares Data 15 noiembrie 2020 11:23:26
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
using namespace std;

bool viz[100001];
int n, m;

void dfs(int i, vector<vector<int>> adj){
    if(viz[i] == false){
        viz[i] = true;
        for(int j = 0; j < adj[i].size(); j++)
            if(viz[adj[i][j]] == false)
                dfs(adj[i][j], adj);
    }
}

int main()
{
    cin >> n >> m;
    vector<vector<int>> adj(n);
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        adj[x-1].push_back(y-1);
        adj[y-1].push_back(x-1);
    }

    int cnt = 0;

    for(int i = 0; i < n; i++){
        if(viz[i] == false){
            dfs(i, adj);
            cnt++;
        }
    }
    cout << cnt;

}