Cod sursa(job #183657)

Utilizator GagosGagos Radu Vasile Gagos Data 22 aprilie 2008 13:56:52
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<stdio.h>
typedef struct nod
{
	int inf;
	nod * urm;
} *pnod;
pnod v[1001];
int n,m,viz[1001],k;
void add(pnod &p,int j)
{
	pnod q;
	q=new nod;
	q->inf=j;
	q->urm=p;
	p=q;
}
void read()
{
	int i,l,j;
	scanf("%d %d",&n,&m);
	for(l=1;l<=m;++l){
		scanf("%d %d",&i,&j);
		add(v[i],j);
		add(v[j],i);
	}
}
/*void write()
{
	printf("Lista de adiacenta :\n");
	for(int i=1;i<=n;++i){
		printf("%d : ",i);
		for(pnod p=v[i];p!=NULL;p=p->urm)
			printf("%d ",p->inf);
		printf("\n");
	}
	printf("\n");
}*/
void DFS(int x)
{
	pnod p;
	viz[x]=1;
	for(p=v[x];p!=NULL;p=p->urm)
		if(!viz[p->inf])
			DFS(p->inf);
}
/*void clean_viz()
{
	for(int i=1;i<=n;++i)
		viz[i]=0;
}*/
int main()
{
	freopen("DFS.in","r",stdin);
	freopen("DFS.out","w",stdout);
	read();
	/*write();
	printf("\nDepth First Search :\n");*/
	for(int i=1;i<=n;++i)
		if(!viz[i]){
			DFS(i);
			k++;
		}
	printf("%d\n",k);
	fcloseall();
	return 0;
}