Cod sursa(job #1140885)

Utilizator Stefanescu_MihaiStefanescu Mihai-Nicolae Stefanescu_Mihai Data 12 martie 2014 12:41:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <vector>

using namespace std;

#define MaxN 100100

bool visited[MaxN];

int s;

int nrvec[MaxN];
vector <int>vec[MaxN];

void dfs( int n )
{
    visited[n] = 1;
    for ( int i = 0; i < nrvec[n]; ++i )
    {
        if ( !visited[vec[n][i]] )
            dfs( vec[n][i] );
    }
}

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

    int n, m;
    int x, y;

    scanf( "%d %d\n", &n, &m );

    for ( ; m; --m )
    {
        scanf( "%d %d\n", &x, &y );

        ++nrvec[x];
        vec[x].push_back(y);

        ++nrvec[y];
        vec[y].push_back(x);
    }

    for ( ; n; --n )
    {
        if ( visited[n] )
            continue;

        ++s;

        dfs( n );
    }

    printf( "%d\n", s );

    fclose( stdin );
    fclose( stdout );

    return 0;
}