Cod sursa(job #411557)

Utilizator O_NealS. Alex O_Neal Data 4 martie 2010 23:09:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<stdio.h>
#include<vector>
using namespace std;
vector<int> a[100001];
	
void df(int n, int pus[100001])
{
	pus[n]=1;
	for(int i=0; i<a[n].size(); ++i)
			if(!pus[a[n][i]])
				df(a[n][i],pus);		
}	

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	int n,m,x,y,contor=0,pus[100001];
	scanf("%d %d",&n,&m);
	for(int i=1; i<=m; i++)
	{
		scanf("%d %d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	memset(pus, 0, sizeof(pus));
	for(int i=1; i<=n; i++)
		if(!pus[i])
		{
			contor++;
			df(i,pus);
		}
	printf("%d ",contor);
	printf("\n");
	return 0;
}