【競プロ精進ログ】【2021/03/27】ABC168: D – .. (Double Dots)

競技プログラミングのための精進履歴をブログ形式で残していきます。

目標は AtCoder 水色！
今のレートは茶色です。

本日の精進ツリーは以下のとおり。

精進ツリー

ABC168: D – .. (Double Dots)
まとめ

ABC168: D – .. (Double Dots)

ABC168 より、ABC168: D – .. (Double Dots)を解きました。
難易度は緑色。

提出コードはこちら。

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
using namespace std;

#define MAX 1000000000

using lint = long long;
using P = pair<int, int>;

/*************************************************************************************
NOTE: 

・BFS 木や BFS による経路復元の典型問題らしい
  https://drken1215.hatenablog.com/entry/2020/06/20/174100
・BFS （始点 s から各頂点 v への最短路を求めるアルゴリズム）で求めた最短経路を復元すると、
  木として表現が可能
*************************************************************************************/

/*************************************************************************************
LOGIC: 
1. まずは、1から各頂点までの最短経路を求める
2. それを逆順にたどるときに BFS木が生まれるので、各頂点の直前のノードが解になる
3. 連結リストなので、常に"Yes"になる
*************************************************************************************/

lint N, M;
vector<vector<lint>> G;

void solve()
{
    vector<lint> dist(N + 1, -1);
    vector<lint> prev(N + 1, -1);
    queue<lint> Q;
    Q.push(1);
    dist[1] = 0;
    while(!Q.empty())
    {
        lint v = Q.front();
        Q.pop();
        for (auto nv : G[v])
        {
            if (dist[nv] == -1)
            {
                dist[nv] = dist[v] + 1;
                prev[nv] = v;
                Q.push(nv);
            }
        }
    }
    cout << "Yes" << endl;
    for (int i = 2; i < N+1; ++i) cout << prev[i] << endl;
}

int main(){
    cin >> N >> M;
    lint a, b;
    G.assign(N+1, vector<lint>());

    rep(i, M){
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    solve();
    return 0;
}