Cod sursa(job #2298423)

Utilizator DavidDragulinDragulin David DavidDragulin Data 8 decembrie 2018 10:15:54
Problema Sate Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
int n,m,x,y,a,b,sol[7502],d1[7502],d2[7502],w[7502];
vector <int> v[7502];
void afis()
{
    fout<<sol[0]<<'\n';
    sort(sol+1,sol+sol[0]+1);
    for(int i=1; i<=sol[0]; i++)
        fout<<sol[i]<<" ";

}
void bfs(int x,int d[])
{
    queue <int> q;
    q.push(x);
    d[x]=1;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        for(int i=0; i<v[nod].size(); i++)
        {
            if(d[v[nod][i]]==0)
        {
            q.push(v[nod][i]);
                d[v[nod][i]]=d[nod]+1;
            }
        }
    }
}

int main()
{
    fin>>n>>m>>x>>y;
    for(int i=1; i<=m; i++)
    {
        fin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    bfs(x,d1);
    bfs(y,d2);
    for (int i=1; i<=n; i++)
        if (d1[i] + d2[i] - 1 == d1[y])
            w[d1[i]]++;
    for (int i=1; i<=n; i++)
        if (d1[i] + d2[i] - 1 == d1[y] && w[d1[i]] == 1)
            sol[++sol[0]] = i;
    afis();
    return 0;
}