Cod sursa(job #250683)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 31 ianuarie 2009 15:32:19
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<stdio.h>
#define N 100005
#define M 200005
/*const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};*/
int *a[N],d[N],x[M],y[M],n,m,viz[N],num;
void bfs(int x0)
{
	int coada[N],u=0,p=0,x,y;
	coada[u++]=x0;
	viz[x0]=1;
	while (u!=p)
	{
		x=coada[p++];
		for (int i=1; i<=a[x][0]; ++i)
		{
			if (!viz[a[x][i]])
			{
				coada[u++]=i;
				viz[a[x][i]]=1;
			}
		}
	}
}
void citire()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	int s=0;
	for (int i=1; i<=m; ++i)
	{
		scanf("%d%d",&x[i],&y[i]);
		++d[x[i]]; 
		++d[y[i]];
	}
	for (int i=1; i<=n; ++i)
	{
		a[i]= new int [1+d[i]];
		a[i][0]=0;
	}
	for (int i=1; i<=m; ++i)
	{
		a[x[i]][++a[x[i]][0]]=y[i];
		a[y[i]][++a[y[i]][0]]=x[i];
	}
	/*
	for (int i=1; i<=n; ++i)
	{
		printf("vecinii lui %d: ",i);
		for (int j=1;j<=a[i][0];++j)
			printf("%d ",a[i][j]);
		printf("\n");
	}	
	printf("%d",n-s);
	*/
	for (int i=1; i<=n; ++i)
	{
		if (!viz[i]) 
			++num;
		bfs(i);
	}
	printf("%d ",num);
}
int main()
{
	citire();
	return 0;
}