Pagini recente » Cod sursa (job #306745) | Cod sursa (job #131374) | Cod sursa (job #1688033) | Cod sursa (job #2561318) | Cod sursa (job #1011492)
#include <fstream>
#include <stdlib.h>
using namespace std;
ifstream cin( "dfs.in" );
ofstream cout( "dfs.out" );
int n, m, x, y, viz[ 100001 ], compConexe;
int *array[ 1000001 ];
void dfs( int k )
{
int i;
viz[ k ] = 1;
for ( i = 1; i <= array[ k ][ 0 ]; i++ )
if ( !viz[ array[ k ][ i ] ] )
dfs( array[ k ][ i ] );
}
int main ()
{
int i;
cin >> n >> m;
for ( i = 1; i <= n; i++ )
{
array[ i ] = ( int * ) realloc( array[ i ], sizeof( int ) );
array[ i ][ 0 ] = 0;
}
for ( i = 1; i <= m; i++ )
{
cin >> x >> y;
array[ x ][ 0 ]++;
array[ x ] = ( int * ) realloc ( array[ x ], ( array[ x ][ 0 ] + 1 ) * sizeof( int ) );
array[ x ][ array[ x ][ 0 ] ] = y;
array[ y ][ 0 ]++;
array[ y ] = ( int * ) realloc ( array[ y ], ( array[ y ][ 0 ] + 1 ) * sizeof( int ) );
array[ y ][ array[ y ][ 0 ] ] = x;
}
for ( i = 1; i <= n; i++ )
if ( !viz[ i ] )
{
compConexe++;
dfs( i );
}
cout << compConexe;
}