Cod sursa(job #870198)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 2 februarie 2013 23:14:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<cstdio>
using namespace std;
int v1[200001],v2[200001],x[100001],*ad[100001];bool v[100000];
void rec(int i)
{
	for(int j=0;j<x[i];++j)
		if(!v[ad[i][j]])
			v[ad[i][j]]=1,rec(ad[i][j]);
}
int main()
{
	freopen("dfs.in","r",stdin);freopen("dfs.out","w",stdout);
	int n,m,i,s=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
		scanf("%d%d",&v1[i],&v2[i]),++x[v1[i]],++x[v2[i]];
	for(i=1;i<=n;x[i++]=0)
		ad[i]=new int[x[i]];
	for(i=1;i<=m;++i)
		ad[v1[i]][x[v1[i]]++]=v2[i],
		ad[v2[i]][x[v2[i]]++]=v1[i];
	for(i=1;i<=n;++i)
		if(!v[i])
			++s,v[i]=1,rec(i);
	printf("%d",s);
}