Cod sursa(job #632274)

Utilizator StefanLacheStefan Lache StefanLache Data 10 noiembrie 2011 19:22:27
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb

#include<stdio.h>
int n,m,i,s[1000],a,b,nr;
typedef struct nod
{
	int info;
	nod *adr;
}*pnod;
pnod v[100000];
void adauga(pnod &dest,int nr)
{
	pnod c;c=new nod;
	c->adr=dest;
	c->info=nr;
	dest=c;
}
void dfs(int nod)
{
	
	pnod p;
	s[nod]=1;
	for(p=v[nod];p!=NULL;p=p->adr)
		if(s[p->info]==0)
			dfs(p->info);
}
int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		adauga(v[a],b);
		adauga(v[b],a);
	}
	for(i=1;i<=n;i++)
		if(s[i]==0)
		{nr++;dfs(i);}
	printf("%d",nr);
	return 0;
}