Cod sursa(job #183948)

Utilizator AndreyPAndrei Poenaru AndreyP Data 22 aprilie 2008 19:47:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<stdio.h>
#define N 100010
int n,m,con;
bool viz[N];
typedef struct nod
{
	int x;
	nod *a;
} *pNod;
pNod v[N];
void add(pNod &dest,int val)
{
	pNod p;
	p=new nod;
	p -> x=val;
	p -> a=dest;
	dest=p;
}
void citeste()
{
	int i,x,y;
	for(i=0; i<m; i++)
	{
		scanf("%d%d",&x,&y);
		add(v[x],y);
		add(v[y],x);
	}
}
void DFS(int nod)
{
	pNod p;
	viz[nod]=true;
	for(p=v[nod]; p!=NULL; p=p->a)
	{
		if(!viz[p->x])
			DFS(p->x);
	}
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	citeste();
	for(int i=1; i<=n; i++)
	{
		if(!viz[i])
		{
			con++;
			DFS(i);
		}
	}
	printf("%d\n",con);
	return 0;
}