Cod sursa(job #411220)

Utilizator crysysdeaconu ioan crysys Data 4 martie 2010 19:27:44
Problema BFS - Parcurgere in latime Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<iostream.h>
#include<fstream.h>
using namespace std;
struct nod{ int inf;
			nod *leg;
}*l[100001];
int d[100001];
void bf(int nodul)
{
	nod *p;
	int ic,sfc,s[100001],c[100001];
	ic=sfc=0;
	s[nodul]=1;
	c[ic]=nodul;
	d[nodul]=0;
	while(ic<=sfc)
	{
		for(p=l[c[ic]];p!=NULL;p=p->leg)
			if(!s[p->inf])
			{
			s[p->inf]=1;
			sfc++;
			c[sfc]=p->inf;
			d[p->inf]=d[c[ic]]+1;
		}
	ic++;
	}
}
int main()
{
	int n,m,s,x,y,i;
	nod *p;
	ifstream f("bfs.in");
	ofstream g("bfs.out");
	f>>n>>m>>s;
	for(i=1;i<=m;i++)
	{
	 f>>x>>y;
		p=new nod;
		if(y!=x)
		{
		p->inf=y;
		p->leg=l[x];
		l[x]=p;
		}
    }
	for(i=1;i<=n;i++)
		d[i]=-1;
	bf(s);
	for(i=1;i<=n;i++)
	g<<d[i]<<" ";
	return 0;
}