Pagini recente » Cod sursa (job #2142697) | Cod sursa (job #1051501) | Cod sursa (job #2143243) | Cod sursa (job #2764421) | Cod sursa (job #2692777)
#include <bits/stdc++.h>
using namespace std;
ifstream f("graf.in");
ofstream g("graf.out");
const int N=75e2+5;
vector <int> mat[N];
int distanta_start[N],distanta_stop[N],nr_ap_distanta[N];
int n,start,stop;
void calc_distanta(int x,int dist[])
{
bitset <N> vizitat;
vizitat[x]=1;
dist[x]=0;
queue <int> q;
q.push(x);
while(!q.empty())
{
int t=q.front();
for(int i=0;i<mat[t].size();i++)
{
int p=mat[t][i];
if(!vizitat[p])
{
dist[p]=dist[t]+1;
vizitat[p]=1;
q.push(p);
}
}
q.pop();
}
}
int main()
{
int m;
f>>n>>m>>start>>stop;
for(int i=1;i<=m;i++)
{
int x,y;
f>>x>>y;
mat[x].push_back(y);
mat[y].push_back(x);
}
int mini=INT_MAX;
calc_distanta(start,distanta_start);
calc_distanta(stop,distanta_stop);
for(int i=1;i<=n;i++)
{
mini=min(mini,distanta_start[i]+distanta_stop[i]);
}
bitset <N> finalizare;
for(int i=1;i<=n;i++)
{
if(distanta_start[i]+distanta_stop[i]==mini)
{
nr_ap_distanta[distanta_start[i]]++;
finalizare[i]=1;
}
}
vector <int> rez;
for(int i=1;i<=n;i++)
{
if(finalizare[i] && nr_ap_distanta[distanta_start[i]]==1)
{
rez.push_back(i);
}
}
g<<rez.size()<<"\n";
for(int i=0;i<rez.size();i++)
{
g<<rez[i]<<" ";
}
return 0;
}