Pagini recente » Cod sursa (job #722171) | Cod sursa (job #2865706) | Cod sursa (job #2585925) | Cod sursa (job #3294646) | Cod sursa (job #367916)
Cod sursa(job #367916)
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;
}