Cod sursa(job #1565857)

Utilizator arlechin96Stavariu Matei arlechin96 Data 11 ianuarie 2016 15:52:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb

#include <vector>
#include <stdio.h>
using namespace std;

vector < int > v[100010];

int  k[100010] , n ,m  , x, y ;
 void  dfs ( int cc , int nod ) 
 {
	k[nod] = cc ;
	for (int i = 0 ; i < (int)v[nod].size(); i++ ) 
		if ( k[v[nod][i]] == 0) 
			dfs(cc , v[nod][i]);	  
 }
int main ()
{
	int i ;
	freopen ( "dfs.in", "r", stdin);
	freopen ( "dfs.out" , "w", stdout);
	scanf ( "%d %d " ,&n, &m) ;
	for ( i = 1 ; i <= m ; i++)
	{
		scanf ( "%d %d", &x, &y) ;
		v[x].push_back(y);
		v[y].push_back(x);
		
	}
	int cc = 0 ;
	for ( i =1 ; i <= n ; i++ ) {
		if (  k[i] == 0 )
		{
			cc++ ;
			dfs (cc, i ) ;
		}
	}
	printf( "%d " , cc);
	return 0 ;
}