Pagini recente » Cod sursa (job #1944800) | Cod sursa (job #193576) | Cod sursa (job #2402114) | Cod sursa (job #3255206) | Cod sursa (job #1911175)
#include <fstream>
#include<iostream>
#include<cstring>
using namespace std;
const int nmax = 7501;
struct node { int x; node * next;};
typedef int sir[nmax];
typedef node* nod;
nod v[nmax];
int *dx, *dy, *num, *vertex, *at, l[nmax];
int n,m,x,y,i,j,xx,yy,nr;
nod p;
ifstream fi("graf.in");
void bfs (int x, int d[])
{ int tail, ttail, head, i;
nod p,q;
memset(d,(n+1)*sizeof(int),0);
head=1; tail=1; ttail=1;
l[1]=x; d[x]=1;
do
{ for (i=head; i<=tail; i++)
{
p = v[l[i]];
while (p!=NULL)
{ if (d[p->x]==0)
{ ttail++;
l[ttail] = p->x;
d[p->x] = d[l[i]]+1;
}
p = p->next;
}
}
if (tail==ttail) break;
head = tail+1;
tail = ttail;
}
while (1);
}
int main()
{
fi>>n>>m>>x>>y;
for (i=1;i<=m;i++)
{ fi>>xx>>yy;
p = new node;
p->x = yy;
p->next = v[xx];
v[xx] = p;
p = new node;
p->x = xx;
p->next = v[yy];
v[yy] = p;
}
dx = new int[n+1];
bfs(x, dx);
dy = new int[n+1];
bfs(y,dy);
num = new int[n+1];
for (i=0;i<=n;i++)
num[i]=0;
vertex = new int[n+1];
for (i=0;i<=n;i++)
vertex[i]=0;
for (i=1;i<=n;i++)
if (dx[i] + dy[i] == dx[y]+1)
{ num[dx[i]]++;
vertex[dx[i]] = i;
}
at = new int[n+1];
for (i=0;i<=n;i++)
at[i]=0;
nr = 0;
for (i=1;i<=n;i++)
if (num[i]==1)
{ nr++;
at[vertex[i]]=1;
}
ofstream fo("graf.out");
fo<<nr<<endl;
for (i=1;i<=n;i++)
if (at[i]==1)
fo<<i<<' ';
return 0;
}