Cod sursa(job #1125652)

Utilizator superman_01Avramescu Cristian superman_01 Data 26 februarie 2014 18:51:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <algorithm>

#define MAX_SIZE 100005

using namespace std;

typedef vector < int > ::iterator vii;

ifstream in ( "dfs.in" );
ofstream out ( "dfs.out" );

vector < int > G[MAX_SIZE] ;
int N ,M ,ccount;
bool used[MAX_SIZE];

void DepthFirstSearch ( int node )
{
	used[node] = true ;
	for( vii it = G[node].begin() ; it != G[node].end() ; ++it )
		if ( !used[*it] )
			DepthFirstSearch ( *it );
}

int main ( void )
{
	int i , j  , x , y;
	in >> N >> M ;
	for ( i = 1 ; i <= M ; ++i )
	{
	    in >> x >> y; 
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for ( i = 1 ; i <= N ; ++i )
		if ( !used[i] )
		DepthFirstSearch( i ) , ++ccount;
	out << ccount << "\n";
	in.close();
	out.close();
	return 0 ;	
}