Pagini recente » Cod sursa (job #1060210) | Cod sursa (job #984284) | Cod sursa (job #1176220) | Cod sursa (job #1753321) | Cod sursa (job #872542)
Cod sursa(job #872542)
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream f("graf.in");
ofstream g("graf.out");
int n,p,u,m,i,x,y,xa,ya,nod,mini,nr,dx[7505],dy[7505],v[7505],c[7505],viz[7505],num[7505],sol[7505];
vector<int>l[7505];
int main()
{
f>>n>>m>>x>>y;
for(i=1;i<=m;++i)
{
f>>xa>>ya;
l[xa].push_back(ya);
l[ya].push_back(xa);
}
c[1]=x;
viz[x]=1;
p=u=1;
dx[x]=1;
while(p<=u)
{
nod=c[p];
++p;
for(vector<int>::iterator it=l[nod].begin();it!=l[nod].end();++it)
if(!viz[*it])
{
viz[*it]=1;
++u;
c[u]=*it;
dx[*it]=dx[nod]+1;
}
}
memset(viz,0,sizeof(viz));
c[1]=y;
p=u=1;
dy[y]=1;
viz[y]=1;
while(p<=u)
{
nod=c[p];
++p;
for(vector<int>::iterator it=l[nod].begin();it!=l[nod].end();++it)
if(!viz[*it])
{
viz[*it]=1;
++u;
c[u]=*it;
dy[*it]=dy[nod]+1;
}
}
mini=dx[y];
for(i=1;i<=n;++i)
if(dx[i]+dy[i]==mini+1)
{
num[dx[i]]++;
v[dx[i]]=i;
}
for(i=1;i<=n;++i)
if(num[i]==1)
{
++nr;
sol[v[i]]=1;
}
g<<nr<<'\n';
for(i=1;i<=n;++i)
if(sol[i])
g<<i<<' ';
g<<'\n';
return 0;
}