Cod sursa(job #349579)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 20 septembrie 2009 11:58:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<stdio.h>
#define nmax 100003

int i, a[nmax],n,m,x,y,nr=0;

typedef struct nod{
	int val;
	nod *p;
} *pnod;

pnod v[nmax];

void add (pnod &dest, int aux)
{
	pnod z;
	z=new nod;
	z->val=aux;
	z->p=dest;
	dest=z;
}
	
void dfs(int nod)
{
	pnod c;
	a[nod]=1;
	for(c=v[nod];c!=NULL;c=c->p)
		if(!a[c->val])
			dfs(c->val);
}
void read()
{
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d", &x, &y);
		add(v[x], y);
		add(v[y], x);
	}
		
}


int main()
{
	read();
	for(i=1;i<=n;i++)
		if(!a[i])
		{
			nr++;
			dfs(i);
		}
	printf("%d\n", nr);
	return 0;
}