Cod sursa(job #323363)

Utilizator syntax_errorGustav Matula syntax_error Data 11 iunie 2009 21:52:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;
typedef vector< int > :: iterator vit;

#define MAXN 100005

int N, M;
int A, B;

int v[ MAXN ];
vector< int > G[ MAXN ];

int dfs( int n ) {
   if( v[ n ] ) return 0;
   v[ n ] = 1;
   
   for( vit i = G[n].begin(); i != G[n].end(); ++i ) 
      dfs( *i );
   
   return 1;
}

int main( void )
{
   freopen( "dfs.in", "r", stdin );
   freopen( "dfs.out", "w", stdout );   
   
   scanf( "%d%d", &N, &M );
   for( int i = 0; i < M; ++i ) {
      scanf( "%d%d", &A, &B ); --A; --B;
      G[ A ].push_back( B );
      G[ B ].push_back( A );
   }   
   
   int Sol = 0;
   
   for( int i = 0; i < N; ++i )
      Sol += dfs( i );
   
   printf( "%d\n", Sol );
   
   return 0;
}