Cod sursa(job #153486)

Utilizator ScrazyRobert Szasz Scrazy Data 10 martie 2008 16:19:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>
#define nm 100003


struct nod{int v;nod* urm;};

nod *A[nm];
int viz[nm];
int n, m;

void dfs(int n)
{
	viz[n]=1;
	nod *p=A[n];
	while(p)
	{
		if (!viz[p->v]) dfs(p->v);
		p=p->urm;
	}
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);

	scanf("%d%d", &n, &m);

	int i, nr=0;

	for (i=1; i<=m; ++i)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		nod *p=new nod;
		p->v=y;
		p->urm=A[x];
		A[x]=p;

        p=new nod;
		p->v=x;
		p->urm=A[y];
		A[y]=p;
	}
	for (i=1; i<=n; ++i)
		if (!viz[i])
			++nr, dfs(i);

	printf("%d\n", nr);
	fclose(stdin);
	fclose(stdout);

	return 0;
}