ABC168D

終わったばかりですが、初めて実戦で幅優先探索を使えて気分が良いので、気持ちが乗っているうちに書いてしまいます。

問題文
あるところに、洞窟があります。
洞窟にはN個の部屋とM本の通路があり、部屋には1からNの、通路には1からMの番号がついています。通路iは部屋Aiと部屋Biを双方向につないでいます。どの2部屋間も、通路をいくつか通って行き来できます。部屋1は洞窟の入り口がある特別な部屋です。
洞窟の中は薄暗いので、部屋1以外の各部屋に1つずつ道しるべを設けることにしました。各部屋の道しるべは、その部屋と通路で直接つながっている部屋の1つを指すように置きます。
洞窟の中は危険なので、部屋1以外のどの部屋についても以下の条件を満たすことが目標です。
• その部屋から出発し、「いまいる部屋にある道しるべを見て、それが指す部屋に移動する」ことを繰り返すと、部屋1に最小の移動回数でたどり着く。
目標を達成できる道しるべの配置が存在するか判定し、存在するならばそのような配置を1つ出力してください。
制約
• 入力はすべて整数
• 2≤N≤10^5
• 1≤M≤2×10^5
• 1≤Ai,Bi≤N (1≤i≤M)
• Ai≠Bi (1≤i≤M)
• どの2部屋間も、通路をいくつか通って行き来できる
入力
入力は以下の形式で標準入力から与えられる。
N M
A1 B1
:
AM BM
出力
目標を達成できる道しるべの配置が存在しなければ No を出力せよ。
存在する場合N行出力せよ。1 行目には Yes を、i (2≤i≤N)行目には部屋iの道しるべが指す部屋の番号を出力せよ。

考え方

問題文がすごくわかりづらい…。
要するに以下2点を解答すればよいことになります。

・任意の部屋から最短距離で部屋１にたどり着くことができるか。
(制約にどの２部屋間も行き来できるって書いてあるので、最短距離は必ずあるのでは…？)
・たどり着ける場合は、それぞれの部屋から最短距離となるために次に進む部屋を出力する。

冒頭にも述べましたが、幅優先探索を使って部屋1から各部屋への最短距離(最小移動回数)を求めていきます。
通路を示す配列は隣接行列にすると、O(N^2)となり間に合わなくなるため、隣接リストを使うことで、O(N)で計算することができます。隣接行列が2次元配列で部屋がつながっているかいないかを全て確認するのに対して、隣接リストはつながっている部屋をリスト形式で追加していくだけなので、無駄なく計算できます。

#include <bits/stdc++.h>
#include <queue>
using namespace std;

int main(){
 int n,m;
 cin >> n >> m;
 
 vector<vector<int>> graph(n,vector<int>(0));//通路を示す隣接リスト
 vector<int> depth(n,-1);//部屋１からの最短距離
 vector<int> path(n);//最短となる道筋、次の部屋
 queue<int> que;
 que.push(0);//スタートの部屋１
 depth[0] = 0;//部屋１は距離0
 
 int a,b;
 for(int i=0; i<m; i++){
   cin >> a >> b;
   a--; b--;
//つながっている部屋を追加
   graph[a].push_back(b);
   graph[b].push_back(a);
 }
 
 while(!que.empty()){
   int v = que.front();
   que.pop();
   
   for(int k : graph[v]){ //部屋vに対してつながっている部屋を見ていく
     if(depth[k] != -1) continue; //すでに調べてあるときは次の処理へ
     depth[k] = depth[v] + 1; //調べてないときは距離を１足す
     path[k] = v; //最短経路となる道すじをメモしておく
     que.push(k);
   }
 }
 
//すべての部屋を回れたか確認
 bool bl = true;
 for(int i=0; i<n; i++){
   if(depth[i] == -1){
     bl = false;
     break;
   }
 }
 
 if(bl){
   cout << "Yes" << endl;
   for(int i=1; i<n; i++){
     cout << path[i] + 1 << endl;
   }
 }
 else{
   cout << "No" << endl;
 }
}

幅優先探索も隣接リストもうまく実装できたので非常に満足。達成感がある。

幅優先探索は以下のページが、グラフとキューの図での説明と実装例があり、とてもわかりやすいです。

BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜

それでは。