Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2877946) | Cod sursa (job #2425665) | Cod sursa (job #2400532)
#include <fstream>
#include <algorithm>
#include <queue>
#define nmax 7501
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
int n,m;
vector<int>v[nmax];
int viz[nmax];
int dx[nmax],dy[nmax];
int x,y;
void read()
{
fin>>n>>m>>x>>y;
int i;
for(i=1; i<=m; i++)
{
int val1,val2;
fin>>val1>>val2;
v[val1].push_back(val2);
v[val2].push_back(val1);
}
}
void bfsX()
{
int i;
queue<int>C;
C.push(x);
while(!C.empty())
{
int node=C.front();
C.pop();
int ct=v[node].size();
for(i=0; i<ct; i++)
{
int val=v[node][i];
if(dx[val]==n) {dx[val]=dx[node]+1; C.push(val);}
}
}
}
void bfsY()
{
int i;
queue<int>C;
C.push(y);
while(!C.empty())
{
int node=C.front();
C.pop();
int ct=v[node].size();
for(i=0; i<ct; i++)
{
int val=v[node][i];
if(dy[val]==n) {dy[val]=dy[node]+1; C.push(val);}
}
}
}
int main()
{
read();
int i;
for(i=1; i<=n; i++)
dx[i]=n;
dx[x]=0;
bfsX();
for(i=1; i<=n; i++)
dy[i]=n;
dy[y]=0;
bfsY();
for(i=1; i<=n; i++)
{
viz[dx[i]]++;
}
int val_min=dx[y];
int ct=0,vec_fin[nmax];
for(i=1; i<=n; i++)
if(dx[i]+dy[i]==val_min)
if(viz[dx[i]]==1) vec_fin[++ct]=i;
fout<<ct<<"\n";
sort(vec_fin+ct,vec_fin+ct+1);
for(i=1; i<=ct; i++)
fout<<vec_fin[i]<<" ";
return 0;
}