Cod sursa(job #402037)
#include<fstream>
#include<iostream>
using namespace std;
struct nod
{
int info;
nod *next;
};
#define nn 14000
nod *g[nn];
int d[nn],n,m,x,y,drum[nn],r[nn];
void adauga(int a,int b)
{
nod *t=new nod;
t->info=b;
t->next=g[a];
g[a]=t;
}
void bfs()
{
int coada[nn],v[nn],st,dr;
st=dr=1;
for(int i=1;i<=n;++i)
v[i]=0;
d[x]=1;
coada[1]=x;
v[x]=1;
while(st<=dr)
{
int k=coada[st];
if(k==y)
break;
for(nod*p=g[k];p;p=p->next)
{
int kk=p->info;
if(!v[kk])
{
coada[++dr]=kk;
v[kk]=1;
d[kk]=d[k]+1;
}
else if(d[k]+1<d[kk])d[kk]=d[k]+1;
}
++st;
}
}
void qsort(int st,int dr)
{
if(st<dr)
{
int i=st,j=dr,aux,d=0;
while(i<=j)
{
if(r[i]>r[j])
{
aux=r[i];
r[i]=r[j];
r[j]=aux;
}
d=1-d;
i+=d;
j-=1-d;
}
qsort(st,i-1);
qsort(i+1,dr);
}
}
void bfs2()
{
int coada[nn],v[nn],st,dr;
st=dr=1;
for(int i=1;i<=n;++i)
v[i]=0;
coada[1]=y;
v[y]=1;
drum[y]=1;
while(st<=dr)
{
int k=coada[st];
if(k==x)
break;
for(nod*p=g[k];p;p=p->next)
{
int kk=p->info;
if(!v[kk])
if(d[kk]==d[k]-1)
{
coada[++dr]=kk;
++drum[d[kk]];
v[kk]=1;
}
}
++st;
}
ofstream fout("graf.out");
m=0;
for(int i=1;i<=st;++i)
if(drum[d[coada[i]]]<2)
{
++m;
r[m]=coada[i];
}
qsort(1,m);
fout<<m<<endl;
for(int i=1;i<=m;++i)
fout<<r[i]<<" ";
}
int main()
{
int a,b;
ifstream fin("graf.in");
fin>>n>>m>>x>>y;
for(;m;--m)
{
fin>>a>>b;
adauga(a,b);
adauga(b,a);
}
bfs();
bfs2();
return 0;
}