Cod sursa(job #184722)

Utilizator AndreyPAndrei Poenaru AndreyP Data 24 aprilie 2008 10:06:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
struct nod
{
	int x,y;
};
nod mu[200010];
int *v[100010],m,n;
bool viz[100010];
int cat[100010];
void citeste()
{
	int i,aux1,aux2;
	for(i=1; i<=m; i++)
	{
		scanf("%d%d",&mu[i].x,&mu[i].y);
		cat[mu[i].x]++;
		cat[mu[i].y]++;
	}
	for(i=1; i<=n; i++)
	{
		v[i]=new int[cat[i]+2];
		v[i][0]=0;
	}
	for(i=1; i<=m; i++)
	{
		aux1=mu[i].x;
		aux2=mu[i].y;
		v[aux1][++v[aux1][0]]=aux2;
		v[aux2][++v[aux2][0]]=aux1;
	}
}
void dfs(int k)
{
	int i;
	viz[k]=true;
	for(i=1; i<=v[k][0]; i++)
	{
		if(!viz[v[k][i]])
			dfs(v[k][i]);
	}
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	citeste();
	int i,r=0;
	for(i=1; i<=n; i++)
	{
		if(!viz[i])
		{
			dfs(i);
			r++;
		}
	}
	printf("%d\n",r);
	return 0;
}