Cod sursa(job #3282312)

Utilizator daniel26mihai daniel daniel26 Data 4 martie 2025 23:20:36
Problema Sate Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <queue>
using namespace std;
ifstream cin("graf.in");
ofstream cout("graf.out");
const int nmax=7501;
vector<int> v[nmax];
set<int> myset;
queue<int> q;
map<int,int> mymap;
int dp[2][nmax];
bool viz[nmax];
int n,m,x,y,a,b,drum;
void bfs(int nod)
{
    q.push(nod);
    while(!q.empty())
    {
        viz[q.front()]=1;
        for(auto e:v[q.front()])
            if(!viz[e])
            {
                viz[e]=1;
                dp[0][e]=dp[0][q.front()]+1;
                q.push(e);
            }
        q.pop();
    }
    while(!q.empty())
        q.pop();
}
void bfs_final(int nod)
{
    q.push(nod);
    while(!q.empty())
    {
        viz[q.front()]=0;
        for(auto e:v[q.front()])
            if(viz[e]==1)
        {
            viz[e]=0;
            dp[1][e]=dp[1][q.front()]+1;
            q.push(e);
        }
        q.pop();
    }
}
int main()
{
    cin>>n>>m>>a>>b;
    myset.insert(a);
    myset.insert(b);
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y;
        v[x].emplace_back(y);
        v[y].emplace_back(x);
    }
    bfs(a);
    bfs_final(b);
    drum=dp[0][b];
    for(int i=1;i<=n;i++)
        if(dp[0][i]+dp[1][i]==drum)
                mymap[dp[0][i]]++;
    for(int i=1;i<=n;i++)
    {
        if(i==a || i==b) continue;
        if(dp[0][i]+dp[1][i]==drum && mymap[dp[0][i]]==1)
            myset.insert(i);
    }
    cout<<myset.size()<<'\n';
    for(auto e:myset)
        cout<<e<<' ';

}