Cod sursa(job #184740)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 24 aprilie 2008 10:24:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>
const int N=100015;
const int M=2*N;
int *a[N],v[N];
bool viz[N];
int n,m;
struct muchie{int x,y;};
muchie e[M];
void df(int x)
{
	viz[x]=true;
	for(int i=1;i<=a[x][0];++i)
		if(!viz[a[x][i]])
			df(a[x][i]);
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out", "w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&e[i].x,&e[i].y);
		++v[e[i].x];
		++v[e[i].y];
	}
	for(int i=0;i<=n;
	a[i]=new int[v[i]+1],
	a[i][0]=0,++i);
	for(int i=1;i<=m;++i)
	{
		int x=e[i].x,y=e[i].y;
		a[x][++a[x][0]]=y;
		a[y][++a[y][0]]=x;
	}
	int i,nr=0;
	for(i=1;i<=n;++i)
		if(!viz[i])
		{
			df(i);
			++nr;
		}
	printf("%d\n",nr);
	return 0;
}