Cod sursa(job #2431812)

Utilizator rd211Dinucu David rd211 Data 20 iunie 2019 20:08:26
Problema Sate Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
vector<int> lista[7510];
bool isViz[7510];
int n;
void addVertex(int x,int y)
{
    lista[x].push_back(y);
    lista[y].push_back(x);
}
void resetbool()
{
    for(int i = 1;i<=n;i++)
        isViz[i]=false;
}
void bfs(int d[],int x)
{
    resetbool();
    queue<int> cue;
    cue.push(x);
    d[x]=0;
    isViz[x]=1;
    while(cue.size())
    {
        int frontOfCue = cue.front();
        for(int i = 0; i<lista[frontOfCue].size(); i++)
        {
            if(!isViz[lista[frontOfCue][i]])
            {
                cue.push(lista[frontOfCue][i]);
                d[lista[frontOfCue][i]]=d[frontOfCue]+1;
                isViz[lista[frontOfCue][i]]=true;
            }
        }
        cue.pop();
    }
}

int main()
{
    int m,x,y,v1,v2;
    int Arr1[7510],Arr2[7510];
    vector<int> r;
    int f[7510];
    fin>>n>>m>>x>>y;
    for(int i = 1; i<=m; i++)
        fin>>v1>>v2,addVertex(v1,v2);
    bfs(Arr1,x);
    bfs(Arr2,y);
    for(int i = 1;i<=n;i++)
    {
        if(Arr1[i]+Arr2[i]==Arr1[y])
        {
            r.push_back(i);
            f[Arr1[i]]++;
        }
    }
    int counter = 0;
    for(int i:r)
    {
        if(f[Arr1[i]]==1)
            counter++;
    }
    fout<<counter<<'\n';
    for(int i:r)
    {
        if(f[Arr1[i]]==1)
            fout<<i<<' ';
    }
    fout<<'\n';
    return 0;
}