Pagini recente » Cod sursa (job #60222) | Cod sursa (job #1163741)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("graf.in");
ofstream g("graf.out");
int n,m,ni,nf,dp[7505],was[7505],niv[7505],numniv[7505],sol[7505],nsol;
vector <int> v[7505];
queue <int> q;
void BFS()
{ int i,nod;
while(!q.empty())
{ nod=q.front(); q.pop();
for(i=0;i<v[nod].size();i++)
if (!dp[v[nod][i]])
{ dp[v[nod][i]]=dp[nod]+1;
q.push(v[nod][i]);
}
}
}
void AntiBFS()
{ int i,nod;
while(!q.empty())
{ nod=q.front(); q.pop();
niv[dp[nod]]++; numniv[dp[nod]]=nod;
for(i=0;i<v[nod].size();i++)
if (!was[v[nod][i]] && dp[v[nod][i]]==dp[nod]-1)
{ was[v[nod][i]]=1;
q.push(v[nod][i]);
}
}
}
int main()
{ int i,x,y;
f>>n>>m>>ni>>nf;
for(i=1;i<=m;i++)
{ f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
q.push(ni); dp[ni]=1;
BFS();
q.push(nf); was[nf]=1;
AntiBFS();
for(i=1;i<=dp[nf];i++)
if (niv[i]==1) {nsol++; sol[nsol]=numniv[i];}
sort(sol+1,sol+nsol+1);
g<<nsol<<"\n";
for(i=1;i<=nsol;i++)
g<<sol[i]<<" ";
return 0;
}