Pagini recente » Cod sursa (job #1938212) | Cod sursa (job #2832813) | Cod sursa (job #685900) | Cod sursa (job #3170679) | Cod sursa (job #1262565)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> g[7501];
int a[7501], q[10001], sol[10001];
bool ok[7501];
int bfs (int x, int destinatie)
{
int p=1, u=1, i, y, nod;
memset(q,0,sizeof(q)); memset(sol,0,sizeof(sol)); memset(ok,0,sizeof(ok));
sol[x]=0; q[p]=x; ok[x]=true;
while (p<=u)
{
nod=q[p];
for (i=0; i<g[nod].size(); i++)
{
if (ok[g[nod][i]]==false)
{
u++;
y=g[nod][i];
q[u]=y;
ok[g[nod][i]]=true;
sol[g[nod][i]]=sol[nod]+1;
if (g[nod][i]==destinatie)
{
return sol[g[nod][i]];
}
}
}
p++;
}
}
int main()
{
int n, m, i, x, y, sursa, destinatie, s, nr=2;
freopen("graf.in","r",stdin);
freopen("graf.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&sursa,&destinatie);
for (i=1; i<=m; i++)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
a[1]=sursa; a[2]=destinatie; s=bfs(sursa,destinatie);
for (i=1; i<=n; i++)
{
if (i==sursa || i==destinatie) continue;
if (bfs(sursa,i)+bfs(i,destinatie)==s)
{
a[++nr]=i;
}
}
printf("%d\n",nr); sort(a+1,a+nr+1);
for (i=1; i<=nr; i++) printf("%d ",a[i]);
fclose(stdin);
fclose(stdout);
return 0;
}