Cod sursa(job #367916)

Utilizator lorandCsorba Lorand-Alexandru lorand Data 23 noiembrie 2009 18:52:15
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
using namespace std;
#include<fstream>
#include<iostream>
#define MAX 104
int a[MAX][MAX], n, start, finish;
int t[MAX];
void read()
{
	ifstream fin("graf.in");
	int m,i,j;
	fin>>n>>m;
	for(; m; --m)
	{
		fin>>i>>j;
		a[i][j]=a[j][i]=1;
	}
	fin>>start>>finish;
	fin.close();
}
void bfs(int start)
{
	int coada[MAX],st=1,dr=1;
	int *v = new int [n+1];
	coada[1]=start;
	for(int i=1;i<=n;i++)
		v[i]=0, t[i]=1;
	v[start]=1;
	t[start]=0;
	while(st<=dr)
	{
		int k=coada[st++];
		for(int i=1;i<=n;i++)
			if(a[k][i]==1 && v[i] == 0)
			{
				coada[++dr]=i;
				v[i]=1;
				t[i]=k;
			}
	}
}
ofstream fout("graf.out");
void drum()
{
	int d[MAX],nrd=0,i;
	if(t[finish]==-1)
	{
		fout<<0;
		fout.close();
		exit(0);
	}
	i=finish;
	while(i)
	{
		d[++nrd]=i;
		i = t[i];
	}
	fout<<nrd<<'\n';
	for(;nrd;nrd--)
		fout<<d[nrd]<<' ';
}
int main()
{
	read();
	bfs(start);
	drum();
	return 0;
}