Cod sursa(job #160194)

Utilizator andreisfrentSfrent Andrei andreisfrent Data 14 martie 2008 20:37:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#define N 100000
#define M 200000
int* la[N+1];
int nv[N+1];
struct muchie
{
	int x,y;
};
muchie vm[M];
int n,m,viz[N+1];
void citeste()
{
	freopen("dfs.in","r",stdin);
	scanf("%d%d\n",&n,&m);
	int i;
	for(i=1;i<=m;++i)
	{
		scanf("%d%d\n",&vm[i].x,&vm[i].y);
		nv[vm[i].x]++;
		nv[vm[i].y]++;
	}		
	for(i=1;i<=n;++i)
	{
		la[i]=new int[nv[i]+1];
		la[i][0]=0;
	}
	for(i=1;i<=m;++i)
	{
		la[vm[i].x][++la[vm[i].x][0]]=vm[i].y;
		la[vm[i].y][++la[vm[i].y][0]]=vm[i].x;		
	}
	fclose(stdin);
}
void df(int x)
{
	viz[x]=1;
	for(int i=1;i<=la[x][0];++i) if(!viz[la[x][i]]) df(la[x][i]);
}
int main()
{
	citeste();
	int cnt=0;
	for(int i=1;i<=n;++i)
	{
		if(!viz[i])
		{
			++cnt;
			df(i);
		}
	}
	freopen("dfs.out","w",stdout);
	printf("%d",cnt);
	fclose(stdout);
	return 0;
}