Pagini recente » Cod sursa (job #1415838) | Cod sursa (job #1850823) | Cod sursa (job #972266) | Cod sursa (job #2291115) | Cod sursa (job #2643109)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define inf 0x3f3f3f
using namespace std;
ifstream in("graf.in");
ofstream out("graf.out");
const int Nmax = 7505;
queue <int>Q;
vector<int>v[Nmax];
int n, m,x,y;
int dx[Nmax],dy[Nmax];
int fr[Nmax];
void bfs(int s, int d[])
{
Q.push(s);
for(int i = 1; i <= n; i++)
d[i]=inf;
d[s]=0;
while(!Q.empty())
{
int k = Q.front();
Q.pop();
for(int i = 0; i < v[k].size(); i++)
{
int vec = v[k][i];
if(d[vec] == inf)
{
d[vec] = d[k] + 1;
Q.push(vec);
}
}
}
}
int main()
{
///n noduri, m muchii
in>>n>>m>>x>>y;
for(int i = 1; i <= m; i++)
{
int a, b;
in>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
bfs(x,dx);
bfs(y,dy);
for(int i = 1; i <= n; i++)
if(dx[i]+dy[i] == dx[y])
fr[dx[i]]++;
int cnt = 0;
for(int i = 1; i <= n; i++)
if(dx[i]+dy[i] == dx[y] && fr[dx[i]] == 1)
cnt++;
out<<cnt<<'\n';
for(int i = 1 ;i <= n; i++)
if(dx[i]+dy[i] == dx[y] && fr[dx[i]] == 1)
out<<i<<' ';
}