Cod sursa(job #2532999)

Utilizator Tudor06MusatTudor Tudor06 Data 28 ianuarie 2020 17:41:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <ctype.h>

using namespace std;

const int NMAX = 1e5;

vector <int> v[NMAX + 1];
bitset<NMAX + 1> vizitat;

void dfs( int nod ) {
    vector<int>::iterator it;
    vizitat[nod] = 1;
    for ( it = v[nod].begin(); it != v[nod].end(); it ++ ) {
        if ( !vizitat[*it] ) {
            dfs( *it );
        }
    }
}

FILE *fin, *fout;

int numar() {
    char ch;
    int nr = 0;
    while ( isspace( ch = fgetc( fin ) ) );
    do {
        nr = nr * 10 + ch - '0';
    } while ( isdigit( ch = fgetc( fin ) ) );
    return nr;
}

int main() {
    fin = fopen( "dfs.in", "r" );
    fout = fopen( "dfs.out", "w" );
    int n, m, i, nod1, nod2, componente;
    n = numar();
    m = numar();
    for ( i = 0; i < m; i ++ ) {
        nod1 = numar();
        nod2 = numar();
        v[nod1].push_back( nod2 );
        v[nod2].push_back( nod1 );
    }
    componente = 0;
    for ( i = 1; i <= n; i ++ ) {
        if ( !vizitat[i] ) {
            componente ++;
            dfs( i );
        }
    }
    fprintf( fout, "%d\n", componente );
    return 0;
}