Cod sursa(job #274331)

Utilizator andr33aradu ioana andr33a Data 9 martie 2009 17:09:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream.h>
ifstream f("dfs.in");
ofstream g("dfs.out");
#define Nmax 100100
long n,m,nr,viz[Nmax];
struct lista
{
	long inf;
	lista *urm;
}*a[Nmax];
void add(long x,long y)
{
	lista * q=new lista;
	q->inf=y;
	q->urm=a[x];
	a[x]=q;
}
void citire()
{
 long x,y;
	f>>n>>m;
	for(long i=1;i<=m;i++)
	{
		f>>x>>y;
		add(x,y);
		add(y,x);
	}
}
void dfs(int x)
{
	lista *c=new lista;
	c->inf=x;
	c->urm=NULL;
	lista *u=c;
	while(c)
	{
		for(lista *q=a[c->inf];q;q=q->urm)
		{
			if(viz[q->inf]==0)
			{
				lista *p=new lista;
				p->inf=q->inf;
				p->urm=NULL;
				u->urm=p;
				u=p;
				viz[q->inf]=1;
			}
		}
		c=c->urm;
	}
}
int main()
{
	citire();
	for(long i=1;i<=n;i++)
		if(viz[i]==0)
		{
			dfs(i);
			nr++;
		}
	g<<nr<<'\n';
 f.close();
 g.close();
 return 0;
}