Cod sursa(job #633956)

Utilizator irene_mFMI Irina Iancu irene_m Data 15 noiembrie 2011 10:43:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <stack>
#include <vector>

using namespace std;

const int MAX_N = 100002;

stack < int > df;
vector < int > edge[ MAX_N ];

int N, M, use[ MAX_N ], nrComp;

void read()
{
	int i, x, y;
	freopen( "dfs.in", "r", stdin );
	scanf( "%d %d", &N, &M );
	for( i = 1; i <= M; ++i )
	{
		scanf( "%d %d", &x, &y);
		edge[ x ].push_back( y );
		edge[ y ].push_back( x );
	}
	fclose(stdin);
}

int next_node( int node )
{
	int i;
	for( i = 0; i < edge[ node ].size(); ++i )
		if( ! use[ edge[ node ][ i ] ] )
			return edge[ node ][ i ];
	return -1;
}

void dfs( int node )
{
	int nodec;
	df.push( node );
	use[ node ] = 1;
	while( ! df.empty() )
	{
		nodec = next_node( df.top() );
		if( nodec == -1 )
			df.pop();
		else
		{
			df.push( nodec );
			use[ nodec ] = 1;
		}
	}
}

void write()
{
	freopen("dfs.out","w",stdout);
	printf( "%d\n", nrComp );
	fclose(stdout);
}
	
int main()
{
	read();
	for( int i = 1; i <= N; ++i )
		if( !use[ i ] )
		{
			nrComp ++;
			dfs( i );
		}
	write();
	return 0;
}