Cod sursa(job #2854343)

Utilizator Victor2006Nicola Victor-Teodor Victor2006 Data 21 februarie 2022 11:33:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <vector>
#define N 100000

std::vector <int> g[N + 1];
int comp[N + 1];
int n;

void dfs( int node ) {
    for ( const int& vecin : g[node] ) {
        if ( comp[vecin] == 0 ) {
            comp[vecin] = comp[node];
            dfs( vecin );
        }
    }
}

inline void addMuchie( int a, int b ) {
    g[a].push_back( b );
    g[b].push_back( a );
}

int main() {
    FILE *fin, *fout;
    int m, a, b;

    fin = fopen( "dfs.in", "r" );
    fscanf( fin, "%d%d", &n, &m );
    for ( int i = 0; i < m; i ++ ) {
        fscanf( fin, "%d%d", &a, &b );
        addMuchie( a, b );
    }
    fclose( fin );

    int cnt = 0;
    for ( int i = 1; i <= n; i ++ ) {
        if ( comp[i] == 0 ) {
            cnt ++;
            comp[i] = cnt;
            dfs( i );
        }
    }

    fout = fopen( "dfs.out", "w" );
    fprintf( fout, "%d\n", cnt );
    fclose( fout );
    return 0;
}