Cod sursa(job #162112)

Utilizator tazuAndrei A. tazu Data 19 martie 2008 14:52:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>
#define N 101000
#define M 201000
int n,m,*a[N],d[N];
bool viz[N];
struct muchie{
	int x,y;
};
muchie v[M];
void citire()
{
	int x,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&v[i].x,&v[i].y);
		++d[v[i].x];
		++d[v[i].y];
	}
	for(int i=1;i<=n;++i){
		a[i]=new int[d[i]+1];
		a[i][0]=0;
	}
	for(int i=1;i<=m;++i){
		a[v[i].x][++a[v[i].x][0]]=v[i].y;
		a[v[i].y][++a[v[i].y][0]]=v[i].x;
	}
}
void dfs(int x)
{
	viz[x]=true;
	for(int i=1;i<=a[x][0];i++)
		if(!viz[a[x][i]])
			dfs(a[x][i]);
}
int componente(){
	int nr=0;
	for(int i=1;i<=n;++i)
		if(!viz[i]){
			dfs(i);
			++nr;
		}
	return nr;
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	citire();
	printf("%d\n",componente());
	return 0;
}