Pagini recente » Cod sursa (job #3166604) | Istoria paginii runda/0001 | Istoria paginii runda/7778 | Cod sursa (job #191951) | Cod sursa (job #2431812)
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
vector<int> lista[7510];
bool isViz[7510];
int n;
void addVertex(int x,int y)
{
lista[x].push_back(y);
lista[y].push_back(x);
}
void resetbool()
{
for(int i = 1;i<=n;i++)
isViz[i]=false;
}
void bfs(int d[],int x)
{
resetbool();
queue<int> cue;
cue.push(x);
d[x]=0;
isViz[x]=1;
while(cue.size())
{
int frontOfCue = cue.front();
for(int i = 0; i<lista[frontOfCue].size(); i++)
{
if(!isViz[lista[frontOfCue][i]])
{
cue.push(lista[frontOfCue][i]);
d[lista[frontOfCue][i]]=d[frontOfCue]+1;
isViz[lista[frontOfCue][i]]=true;
}
}
cue.pop();
}
}
int main()
{
int m,x,y,v1,v2;
int Arr1[7510],Arr2[7510];
vector<int> r;
int f[7510];
fin>>n>>m>>x>>y;
for(int i = 1; i<=m; i++)
fin>>v1>>v2,addVertex(v1,v2);
bfs(Arr1,x);
bfs(Arr2,y);
for(int i = 1;i<=n;i++)
{
if(Arr1[i]+Arr2[i]==Arr1[y])
{
r.push_back(i);
f[Arr1[i]]++;
}
}
int counter = 0;
for(int i:r)
{
if(f[Arr1[i]]==1)
counter++;
}
fout<<counter<<'\n';
for(int i:r)
{
if(f[Arr1[i]]==1)
fout<<i<<' ';
}
fout<<'\n';
return 0;
}