Cod sursa(job #757528)

Utilizator matei_cChristescu Matei matei_c Data 12 iunie 2012 16:13:37
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<cstdio>
#include<iostream>
#include<vector>

using namespace std;

#define maxn 100000
#define maxm 1000000

vector <int> Vecini[maxn];
int N, M;
bool sel[maxn] ;

void df(int nod)
{
	sel[nod] = true ;
	for(size_t i=0;i<Vecini[nod].size();++i)
	{	
		if( sel[ Vecini[nod][i] ] == false)
		{
			sel[ Vecini[nod][i] ] = true ;
			df( Vecini[nod][i] ) ;
		}
	}	
}

int main()
{ 
	
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	scanf("%d%d",&N,&M);
	
	for(int i=1;i<=M;++i)
	{
		int a,b ;
		scanf("%d %d", &a, &b);
		Vecini[a].push_back(b);
		Vecini[b].push_back(a);
	}
	
	int nr = 0 ;
	for(int i=1;i<=N;++i)
	{
		if( sel[i] == false )
		{
			df(i) ;
			++ nr ;
		}	
	}
	
	printf("%d\n",nr);
	
	return 0 ;
	
}