Cod sursa(job #3041993)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 3 aprilie 2023 14:05:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ( "dfs.in" );
ofstream fout ( "dfs.out" );

const int N = 1e5;
vector <int> g[N + 1];
int viz[N + 1];

void dfs ( int x ) {
    
    viz[x] = 1;
    
    for ( int i = 0; i < g[x].size(); i++ ) {
        if ( viz[g[x][i]] == 0 ) {
            viz[g[x][i]] = 1;
            dfs (g[x][i]);
        }
    }
}

int main() {
    
    int n, m, i, a, b, cnt = 0;
    
    fin >> n >> m;
    
    for ( i = 0; i < m; i++ ) {
        
        fin >> a >> b;
        
        g[a].push_back (b);
        g[b].push_back (a);
    }
    
    for ( i = 1; i <= n; i++ ) {
        if ( viz[i] == 0 ) {
            dfs (i);
            cnt++;
        }
    }
    
    fout << cnt;
    
    return 0;
}