ABC168に参加してみました - インフラエンジニアの備忘録とか色々

初めに

ABC168に参加しました。今回は久しぶりにA・B・Cが解けました。
D問題に関してはBFS(幅優先探索)すれば行けるだろうなと思ってコーティングしている途中で終わってしまいました。
もうちょっとC問題が早く解ければ行けそうだったんですよね～。。。
なので、今回はD問題について書いて行きます！

https://atcoder.jp/contests/abc168

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

D - .. (Double Dots)

N個の部屋と、部屋と部屋を繋ぐ通路がM本あります。各部屋には繋がっている部屋を
指す道しるべを一つ配置することができます。
部屋と部屋との通路の情報が与えるのでその情報を元に、ある部屋から出口に繋がっている部屋1に
最小の移動回数で移動できるような道しるべの配置が存在するか判定する問題です。

解説を見てからの回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){

ll N,M;
vector<ll> load[100005];

cin >> N >> M;

for(ll i = 0;i < M;++i){

    ll A,B;    

    cin >> A >> B;

    // ①隣接リストを作成
    A--;B--;
    load[A].push_back(B);
    load[B].push_back(A);

}

    // ②BFS のためのデータ構造
    vector<ll> dist(N, -1); // 全頂点を「未訪問」に初期化
    vector<ll> pre(N,-1);
    queue<ll> que;

    // 初期条件 (頂点 0 を初期ノードとする)
    dist[0] = 0;
    que.push(0); // 0 を頂点にする

    while (!que.empty()) {

　　// ③キューから先頭頂点を取り出す
        ll v = que.front(); 
        que.pop();

        // ④v から辿れる頂点をすべて調べる
        for (int nv : load[v]) {

            // ⑤すでに発見済みの頂点は探索しない
            if (dist[nv] != -1) continue; 

            // ⑥新たな頂点 nv について距離情報・辿ってきた頂点情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            //道しるべの配置を記録
            pre[nv] = v;
            que.push(nv);

        }
    }

bool flg = true;

// 未到達の頂点が無いか確認
for(ll i = 0;i < N;++i) if(dist[i] == -1) flg = false;

// すべての頂点に到達していた場合
if(flg){

    cout << "Yes" << endl;

    // 結果出力 (各頂点の頂点 0 からの距離を見る)
    for (ll v = 0; v < N; ++v){

        if(v == 0) continue;
        ll ans = pre[v];
        ans++;
        cout << ans << endl;

    } 

}
// 到達していない頂点があった場合 
else{

        cout << "No" << endl;

}

return 0;

}

与えられた通路情報を元に出口に繋がっている部屋1から、それぞれの部屋への最短経路を求めれば良いので以下①～⑥にてBFSを行います。

　①まずは、入力された通路の情報を隣接リストに格納します。
　(隣接リストのイメージは以下のような感じ赤枠が隣接している要素のリスト)