Cod sursa(job #2721715)

Utilizator Victor2006Nicola Victor-Teodor Victor2006 Data 12 martie 2021 10:07:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
#define N 100000

using namespace std;

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

vector <int> g[N + 1];
char parcurs[N + 1];

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

int main() {
    int n, m, x, y, cnt;
    fin >> n >> m;
    for ( int i = 1; i <= m; i ++ ) {
        fin >> x >> y;
        g[x].push_back( y );
        g[y].push_back( x );
    }
    cnt = 0;
    for ( int i = 1; i <= n; i ++ ) {
        if ( !parcurs[i] ) {
            parcurs[i] = 1;
            dfs( i );
            cnt ++;
        }
    }
    fout << cnt << "\n";
    return 0;
}