Cod sursa(job #291694)

Utilizator daiana.ppaschia daiana daiana.p Data 30 martie 2009 10:45:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream.h>
int viz[100000];
struct nod
{
	int varf;
	nod *adr;
} *coada[100000];

void add(long x, long y)
{
	nod *aux;
	aux=new nod;
	aux->varf=y;
	aux->adr=coada[x];
	coada[x]=aux;
}

void dfs(long a)
{
	nod *aux;
	aux=coada[a];
	viz[a]=1;
	while (aux!=NULL)
		{if (!viz[aux->varf])
			dfs(aux->varf);
		 aux=aux->adr;
		}
}

int main()
{
	long nr=0,n,m,i,a,b;
	ifstream f ("dfs.in");
	ofstream out ("dfs.out");
	f>>n>>m;
	for (i=1;i<=m;i++)
		{f>>a>>b;
		 add(a,b);
		 add(b,a);
		}
	for (i=1;i<=n;i++)
		if (!viz[i])
			{dfs(i);
			 nr++;
			}
	out<<nr;;
	return 0;
}