Cod sursa(job #2643109)

Utilizator cristiemanuelstroe cristian emanuel cristiemanuel Data 18 august 2020 18:49:37
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include    <iostream>
#include    <fstream>
#include    <queue>
#include    <vector>
#define inf 0x3f3f3f

using namespace std;

ifstream in("graf.in");
ofstream out("graf.out");

const int Nmax = 7505;
queue <int>Q;
vector<int>v[Nmax];
int n, m,x,y;
int dx[Nmax],dy[Nmax];
int fr[Nmax];

void bfs(int s, int d[])
{
    Q.push(s);
    for(int i = 1; i <= n; i++)
        d[i]=inf;
    d[s]=0;
    while(!Q.empty())
    {
        int k = Q.front();
        Q.pop();
        for(int i = 0; i < v[k].size(); i++)
        {
            int vec = v[k][i];
            if(d[vec] == inf)
            {
                d[vec] = d[k] + 1;
                Q.push(vec);
            }
        }
    }
}

int main()
{
       ///n noduri, m muchii
      in>>n>>m>>x>>y;
      for(int i = 1; i <= m; i++)
      {
          int a, b;
          in>>a>>b;
          v[a].push_back(b);
          v[b].push_back(a);
      }
     bfs(x,dx);
     bfs(y,dy);
     for(int i = 1; i <= n; i++)
        if(dx[i]+dy[i] == dx[y])
           fr[dx[i]]++;
     int cnt = 0;
     for(int i = 1; i <= n; i++)
        if(dx[i]+dy[i] == dx[y] && fr[dx[i]] == 1)
           cnt++;
     out<<cnt<<'\n';
     for(int i = 1 ;i <= n; i++)
        if(dx[i]+dy[i] == dx[y] && fr[dx[i]] == 1)
           out<<i<<' ';
}