Cod sursa(job #275277)

Utilizator cotofanaCotofana Cristian cotofana Data 10 martie 2009 12:44:45
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>
#define dim 100

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

int n, m, fol[dim+1]={0}, ct=0;
nod *prim[dim+1];

void dfs(nod *n1)
{
	while (n1)
	{
		if (!fol[n1->nr])
		{
			fol[n1->nr]=1;
			dfs(prim[n1->nr]);
		}
		n1=n1->urm;
	}
}

void add(nod *&p, int nr)
{
	nod *n1=new nod;
	n1->nr=nr;
	n1->urm=p;
	p=n1;
}

int main()
{
	int i, a, b;
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	scanf("%d %d\n", &n, &m);
	for (i=1; i<=m; i++)
	{
		scanf("%d %d\n", &a, &b);
		add(prim[a], b);
		add(prim[b], a);
	}
	for (i=1; i<=n; i++)
		if (!fol[i])
		{
			ct++;
			dfs(prim[i]);
		}
	printf("%d\n", ct);
	return 0;
}