Cod sursa(job #401213)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 22 februarie 2010 17:08:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int v[100001],cc;

vector <int> c[100001];

void cpcn(int x)
{
	int i,len=c[x].size();
	for (i=0;i<len;i++)
		if (!v[c[x][i]])
		{
			v[c[x][i]]=1;
			cpcn(c[x][i]);
		}
}

int main()
{
	int i,n,m,a,b;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<m+1;i++) 
	{
		scanf("%d%d",&a,&b);
		c[a].push_back(b);
		c[b].push_back(a);
	}
	for (i=1;i<n+1;i++)
	{
		if (!v[i]) 
		{
			v[i]=1;
			++cc;
			cpcn(i);
		}
	}
	printf("%d",cc);
	return 0;
}