Cod sursa(job #1011492)

Utilizator drobertDumitru Robert drobert Data 16 octombrie 2013 21:37:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#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;
}