Cod sursa(job #280570)

Utilizator Andrei_ScorpioAndreiana Andrei Daniel Andrei_Scorpio Data 13 martie 2009 14:17:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream.h>
#define Nmax 100100
ifstream f("dfs.in");
ofstream g("dfs.out");

int nr,n,m,viz[Nmax];

struct coada
{
int inf;
coada *urm;
}*c;

struct elem
{
int inf;
elem *urm;
}*a[Nmax];

void citire()
{
 elem *p;
 int x,y,i;
 f>>n>>m;
 for(i=1;i<=m;i++)
 {
	f>>x>>y;
	p=new elem;
	p->inf=y;
	p->urm=a[x];
	a[x]=p;
	p=new elem;
	p->inf=x;
	p->urm=a[y];
	a[y]=p;
 }
}

void program(int s)
{

 elem *p;
 viz[s]=1;
 coada *ultim,*q;
 c=new coada;
 c->inf=s;
 c->urm=NULL;
 ultim=c;
 while(c!=NULL)
 {
	p=a[c->inf];
	while(p)
	{
		if(viz[p->inf]==0)
		{
		viz[p->inf]=1;
		q=new coada;
		q->inf=p->inf;
		q->urm=NULL;
		ultim->urm=q;
		ultim=q;
		}
		p=p->urm;
	}
	c=c->urm;
 }
}

int main()
{
 citire();
 for(int i=1;i<=n;i++)
	if(viz[i]==0)
	{	program(i);
		nr++;
	}
 g<<nr<<'\n';
 g.close();
 return 0;
}