Cod sursa(job #276577)

Utilizator dan_10Dan Alexandru dan_10 Data 11 martie 2009 11:18:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>

struct nod{	int x;
		nod *next;
	    };
nod *v[100010];
long n,m;
long pus[100010];

void citire()
{	freopen("dfs.in","r",stdin);
	scanf("%ld %ld",&n,&m);

	long a,b;
	nod *p;
	for(long i=1;i<=m;i++)
	     {	scanf("%ld %ld",&a,&b);
		p=new nod;
		p->x = b;
		p->next = v[a];
		v[a] = p;
		p=new nod;
		p->x = a;
		p->next = v[b];
		v[b] = p;
	     }
}
void df(long k)
{	  pus[k]=1;
		nod *p;
		p=v[k];  	
           while (p!=NULL)
			{   if (pus[p->x]==0) df(p->x);
			   p=p->next;
			 }			
		
}
int main()
{	citire();

	freopen("dfs.out","w",stdout);
	long cont=0;
	for(long i=1;i<=n;i++)
		 if(pus[i]==0){		df(i);
		 					cont++;
						}  				
	printf("%d\n",cont);
	return 0;
}