Pagini recente » Cod sursa (job #2998844) | Cod sursa (job #1165089) | Cod sursa (job #2729038) | Cod sursa (job #2742691) | Cod sursa (job #2967553)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream in("graf.in");
ofstream out("graf.out");
const int NMAX = 7501;
int frcv[NMAX], distX[NMAX], distY[NMAX];
vector <int> v[NMAX];
int start, finish, n, nrmoduri;
void bfs( int start_node, int dist[]){
queue <int> coada;
coada.push(start_node);
for( int i = 1 ; i <= n ; i++ )
dist[i] = -1;
dist[start_node] = 0;
while(!coada.empty()){
int nod = coada.front();
coada.pop();
for( int i = 0 ; i < v[nod].size(); i++ ){
if( dist[v[nod][i]] == -1 ){
coada.push(v[nod][i]);
dist[v[nod][i]]=dist[nod]+1;
}
}
}
}
int main()
{
int m, a, b;
in >> n >> m >> start >> finish;
for( int i = 0 ; i < m ; i++ ){
in >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
bfs(start, distX);
bfs(finish, distY);
for( int i = 1 ; i <= n ; i++ )
if( distX[i] + distY[i] == distX[finish] ){
frcv[distX[i]]++;
}
vector <int> ans;
for( int i = 1 ; i <= n ; i++ )
if( distX[i] + distY[i] == distX[finish] && frcv[distX[i]] == 1 )
ans.push_back(i);
out << ans.size() << endl;
for( int i = 0 ; i < ans.size() ; i++ )
out << ans[i] << " ";
return 0;
}