Cod sursa(job #794445)

Utilizator MtkMarianHagrSnaf MtkMarian Data 6 octombrie 2012 12:36:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<cstdio>
#include<vector>
#include<string.h>

using namespace std;

#define NMAX 100005



vector <int> *a;

int *lsize;
int n,m,nr=0,x,y;
void dfs(int k)
{
	int y;
	int x=lsize[k];
	lsize[k]=-1;
		for(int i=0;i<x;++i)
		{
				y=a[k][i];
			
			if(lsize[y]>=0)
			{				
				dfs(y);
				
			}
			
		}
	
		
				
}
	



int main()
{

	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	scanf("%d %d",&n,&m);

	a=new vector <int> [n+2];
	lsize=new int[n+3];
	memset(&lsize[0],0,(n+2)*sizeof(int));

	for(int i=1;i<=m;++i)
	{
		scanf("%d %d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
		++lsize[y];
		++lsize[x];
	
	}
	
	
  
	for(int i=1;i<=n;++i)
		if(lsize[i]>=0)
			{				
				
				dfs(i);				
				++nr;
			}
		
		printf("%d\n",nr);



	return 0;
}