Cod sursa(job #2672879)

Utilizator CRaresCroicia Rares CRares Data 15 noiembrie 2020 11:27:31
Problema Parcurgere DFS - componente conexe Scor 100
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;
vector<int> adj[500005];

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

int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    cin >> n >> m;

    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);
            cnt++;
        }
    }
    cout << cnt;

}