Cod sursa(job #2759227)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 16 iunie 2021 12:03:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <vector>

#define MAX_N 100000

using namespace std;

int viz[MAX_N];
vector <int>muchii[MAX_N];

void fill( int nod ) {
    int i;

    viz[nod] = 1;
    for ( i = 0; i < muchii[nod].size(); i++ ) {
        if ( !viz[muchii[nod][i]] )
            fill( muchii[nod][i] );
    }
}

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

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

    comp = 0;
    for ( i = 0; i < n; i++ ) {
        if ( !viz[i] ) {
            fill( i );
            comp++;
        }
    }

    fout = fopen( "dfs.out", "w" );
    fprintf( fout, "%d", comp );
    fclose( fout );

    return 0;
}