Pagini recente » Cod sursa (job #6513) | Cod sursa (job #172408) | Rating Jerdea Florin (ursu-vali) | Cod sursa (job #1056835) | Cod sursa (job #3282312)
#include <fstream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <queue>
using namespace std;
ifstream cin("graf.in");
ofstream cout("graf.out");
const int nmax=7501;
vector<int> v[nmax];
set<int> myset;
queue<int> q;
map<int,int> mymap;
int dp[2][nmax];
bool viz[nmax];
int n,m,x,y,a,b,drum;
void bfs(int nod)
{
q.push(nod);
while(!q.empty())
{
viz[q.front()]=1;
for(auto e:v[q.front()])
if(!viz[e])
{
viz[e]=1;
dp[0][e]=dp[0][q.front()]+1;
q.push(e);
}
q.pop();
}
while(!q.empty())
q.pop();
}
void bfs_final(int nod)
{
q.push(nod);
while(!q.empty())
{
viz[q.front()]=0;
for(auto e:v[q.front()])
if(viz[e]==1)
{
viz[e]=0;
dp[1][e]=dp[1][q.front()]+1;
q.push(e);
}
q.pop();
}
}
int main()
{
cin>>n>>m>>a>>b;
myset.insert(a);
myset.insert(b);
for(int i=1; i<=m; i++)
{
cin>>x>>y;
v[x].emplace_back(y);
v[y].emplace_back(x);
}
bfs(a);
bfs_final(b);
drum=dp[0][b];
for(int i=1;i<=n;i++)
if(dp[0][i]+dp[1][i]==drum)
mymap[dp[0][i]]++;
for(int i=1;i<=n;i++)
{
if(i==a || i==b) continue;
if(dp[0][i]+dp[1][i]==drum && mymap[dp[0][i]]==1)
myset.insert(i);
}
cout<<myset.size()<<'\n';
for(auto e:myset)
cout<<e<<' ';
}