Cod sursa(job #1492948)

Utilizator DobosDobos Paul Dobos Data 28 septembrie 2015 14:36:25
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("graf.in");
ofstream fout ("graf.out");
vector <int> q[7505];
int v[7505],d[7505];
deque < int > lx;
inline void dfs()
{
    int x;
    while(!lx.empty()){
        x = lx.front();
        lx.pop_front();
    for(int i  = 0 ; i < q[x].size(); i ++){
        if(v[q[x][i]] == -1){
            v[q[x][i]] = v[x] + 1;
            lx.push_back(q[x][i]);
           d[q[x][i]] = d[x];
        }
        else
        if(v[q[x][i]] == v[x] + 1){
            d[q[x][i]]++;
        }
    }
    }
}
int main()
{
    int n , m,x,y,a,b;
    fin >> n >> m >> x >> y;
    for(int i = 1 ; i <= m; i++){
        fin >> a >> b;
        q[a].push_back(b);
        q[b].push_back(a);
    }
    memset(v,-1,sizeof(v));
    lx.push_back(x);
    v[x] = 0;
    dfs();
    int e = 0;
    for(int i = 1; i <= n ; i++)
        if(d[i] == d[y])
            lx.push_back(i),e++;
    lx.push_back(x);
    sort(lx.begin() , lx.begin() + e + 1);
        fout << e + 1 << "\n";
        for(int i = 0; i < lx.size();i++)
            fout << lx[i] << " ";
    return 0;
}