Cod sursa(job #2400532)

Utilizator stan_flaviusStan Flavius Stefan stan_flavius Data 8 aprilie 2019 20:34:50
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <algorithm>
#include <queue>
#define nmax 7501
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");

int n,m;
vector<int>v[nmax];
int viz[nmax];
int dx[nmax],dy[nmax];
int x,y;

void read()
{
    fin>>n>>m>>x>>y;
    int i;
    for(i=1; i<=m; i++)
       {
           int val1,val2;
           fin>>val1>>val2;
           v[val1].push_back(val2);
           v[val2].push_back(val1);
       }
}

void bfsX()
{
    int i;
    queue<int>C;
    C.push(x);

    while(!C.empty())
         {
             int node=C.front();
             C.pop();

             int ct=v[node].size();
             for(i=0; i<ct; i++)
                 {
                   int val=v[node][i];
                   if(dx[val]==n) {dx[val]=dx[node]+1; C.push(val);}
                 }
         }
}

void bfsY()
{
    int i;
    queue<int>C;
    C.push(y);

    while(!C.empty())
         {
             int node=C.front();
             C.pop();

             int ct=v[node].size();
             for(i=0; i<ct; i++)
                 {
                   int val=v[node][i];
                   if(dy[val]==n) {dy[val]=dy[node]+1; C.push(val);}
                 }
         }
}

int main()
{
    read();
    int i;
    for(i=1; i<=n; i++)
         dx[i]=n;
    dx[x]=0;
    bfsX();
    for(i=1; i<=n; i++)
         dy[i]=n;
    dy[y]=0;
    bfsY();
    for(i=1; i<=n; i++)
        {

            viz[dx[i]]++;
        }
    int val_min=dx[y];
    int ct=0,vec_fin[nmax];
    for(i=1; i<=n; i++)
         if(dx[i]+dy[i]==val_min)
            if(viz[dx[i]]==1) vec_fin[++ct]=i;

    fout<<ct<<"\n";
    sort(vec_fin+ct,vec_fin+ct+1);
    for(i=1; i<=ct; i++)
         fout<<vec_fin[i]<<" ";
    return 0;
}