バレー・ボール [PG BATTLE 2019 せんべい C]

https://products.sint.co.jp/hubfs/resource/topsic/pgb/2-3.pdf

前提知識

• BFS

解説

入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください

公式解説

選手を頂点、パスを辺とすると無向グラフとみなすことができる。
問われている、高橋君にボールを送り返せるかというのは、到達可能性判定である。
グラフ上での到達可能性判定といえば、BFSで解けることが知られている。
行動回数も考慮する必要があるので、(選手)という頂点ではなく、(頂点,行動回数)として頂点を増やして対応する。
あとは、特に注意点も無いが、BFSで到達可能性判定をやったことが無いと、ここまで来れないだろう。
競技プログラミングでBFSを使う解説はインターネットに多くあるので、他で学習してからこちらに戻ってくるといいだろう。

さて、この問題では、各選手についてサービスされたときに高橋くんに3回以下の行動で送れるかの判定であるが、
パスは双方向に出すことができるため、高橋くんから3回以下の行動でパスがその選手に渡せる事ができれば、
逆にその選手が3回以下の行動でパスを渡せることになる。
なので、高橋くんから各選手について3回以下の行動でパスを渡せるかをBFSで判定しよう。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/

int N, M;
vector<int> E[101010];
bool vis[101010][4];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    queue<pair<int, int>> que;
    vis[0][0] = true;
    que.push({0, 0});

    while(!que.empty()) {
        auto q = que.front();
        que.pop();
        int cu = q.first;
        int pass = q.second;
        if (pass == 3) continue;
        fore(to, E[cu]) if (!vis[to][pass + 1])
        {
            vis[to][pass + 1] = true;
            que.push({to, pass + 1});
        }
    }

    rep(i, 1, N + 1) {
        bool ok = false;
        rep(j, 0, 4) if (vis[i][j]) ok = true;
        if (ok) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}