Cod sursa(job #213500)

Utilizator sory1806Sandu Sorina-Gabriela sory1806 Data 9 octombrie 2008 23:05:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
int n, m, viz[100005], cnt;
typedef struct nod
{	int x;
	nod *a;
}      	*pNod;
pNod v[100005];

void citire()
{       int i, x, y;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);
	pNod p;
	for(i=1; i<=m; i++)
	{   	scanf("%d %d",&x,&y);
		p=new nod;
		p->x=x;
		p->a=v[y];
		v[y]=p;
		p=new nod;
		p->x=y;
		p->a=v[x];
		v[x]=p;
	}
}

void DFS(int nod)
{      	pNod p;
	viz[nod]=1;
	for(p=v[nod]; p!=NULL; p=p->a)
		if(!viz[p->x])
			DFS(p->x);
}

int main()
{      	citire();
	int i;
	for(i=1; i<=n; i++)
		if(!viz[i])
		{ 	cnt++;
			DFS(i);
		}
	printf("%d\n", cnt);
	return 0;
}