Cod sursa(job #1889211)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 22 februarie 2017 17:05:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;

#define NMAX 100005

int a[ NMAX ];

vector < int > v[ NMAX ];
stack < int > Q;

void DFS ( int start ) {

    int i, n, m;

    a[ start ] = 1;
    Q.push( start );

    while ( !Q.empty() ) {
        m = Q.top();
        Q.pop();
        n = v[ m ].size();
        for ( i = 0; i < n; ++i ) {
            if ( !a[ v[ m ][ i ] ] ) {
                a[ v[ m ][ i ] ] = 1;
                Q.push(  v[ m ][ i ] );
            }
        }
    }


}

int main () {

    freopen( "dfs.in", "r", stdin );
    freopen( "dfs.out", "w", stdout );

    int n, m, i, j, x, y, s;

    scanf( "%d%d",&n,&m );
    while ( m-- ) {
        scanf( "%d%d",&x,&y );
        v[ x ].push_back( y );
        v[ y ].push_back( x );
    }

    s = 0;
    for ( i = 1; i <= n; ++i ) {
        if ( !a[ i ] ) {
            DFS( i );
            s++;
        }
    }

    printf( "%d", s );

    return 0;

}