Cod sursa(job #671509)

Utilizator OanaCristinaFlorescu Oana Cristina OanaCristina Data 31 ianuarie 2012 16:47:48
Problema BFS - Parcurgere in latime Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");

int n,m,S[100001],d[100001],start;
int c[100001],li=1,ls=0;

struct nod
{
	int inf;
	nod* next;
};

nod* LA[100001];

int coadavida()
{
	return li>ls;
}

void pune(int x)
{
	ls++;
	c[ls]=x;
}

int  extragere()
{
	int x=c[li];
	li++;
	return x;
}


void BF(int start)
{
	S[start]=1;
	pune(start);
	while(!coadavida())
	{
		int x=extragere();
		nod* nc=LA[x];
		while(nc)
		{
			int vecin=nc->inf;
			if(!S[vecin])
			{
				S[vecin]=1;
				d[vecin]=d[x]+1;
				pune(vecin);
			}
			nc=nc->next;
		}
	}
}

void add(int x,int y)
{
	nod* n=new nod;
	n->inf=y;
	n->next=LA[x];
	LA[x]=n;
}

void citire()
{
	in>>n>>m>>start;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		in>>x>>y;
		add(x,y);
	}
}

int main()
{
	citire();
	BF(start);
	for(int i=1;i<=n;i++)
		if(d[i]==0 && i!=start)
			d[i]=-1;
	for(int i=1;i<=n;i++)
		out<<d[i]<<" ";
	return 0;
}