問題
要約
-
洞窟には N 個の部屋と M 本の通路がある。
-
部屋には1からNまで、通路には1からMまでの番号がついている。
-
通路 i は部屋 A_i と部屋 B_i を双方向につないでいる。
-
部屋1は洞窟の入り口で、特別な部屋である。
-
部屋1以外の各部屋に1つずつ道しるべを設置する。
-
道しるべは、その部屋と直接つながっている部屋の1つを指す。
-
目標を達成できる道しるべの配置が存在するかどうかの判定
-
存在する場合、そのような配置の1つを出力すること
既存投稿一覧ページへのリンク
アプローチ
- グラフを構築し、幅優先探索（BFS）を用いて部屋1から各部屋への最短経路を求める。
- BFSの過程で、各部屋の親（最短経路で1つ前の部屋）を記録する。
- 各部屋の道しるべを、その親を指すように設定する。
解法手順
- 入力を受け取り、隣接リスト形式でグラフを構築する。
- BFSのために必要なデータ構造を初期化する：
- 訪問済みフラグ（visit）
- 部屋1からの距離（D）
- 親ノード（P）
- キュー（Q）
- 部屋1をキューに入れ、BFSを開始する。
- キューが空になるまで以下を繰り返す：
- キューから部屋を取り出す。
- その部屋に隣接する未訪問の部屋について：
- 訪問済みとマークする。
- 部屋1からの距離を記録する。
- 親ノードを記録する。
- キューに追加する。
- BFSが終了したら、"Yes"を出力する（必ず解が存在するため）。
- 部屋2以降について、各部屋の親ノード（道しるべが指す部屋）を順に出力する。
ACコード
ac.py
from collections import deque
def io_func():
# 部屋の数nと通路の数mを入力として受け取る
n, m = map(int, input().split())
# 通路の情報を入力として受け取る
edges = [map(int, input().split()) for _ in range(m)]
return n, m, edges
def solve(n, m, edges):
# グラフを隣接リスト形式で構築
G = [[] for _ in range(n+1)]
for a, b in edges:
G[a].append(b)
G[b].append(a)
# BFSのためのデータ構造を初期化
visit = [False] * (n+1) # 訪問済みフラグ
D = [0] * (n+1) # 部屋1からの距離
P = [0] * (n+1) # 親ノード
Q = deque([(1, 0)]) # キュー（部屋番号, 距離）
visit[1] = True # 部屋1を訪問済みとマーク
# BFSを実行
while Q:
u, d = Q.popleft()
for v in G[u]:
if not visit[v]:
visit[v] = True
D[v] = d + 1
P[v] = u
Q.append((v, d + 1))
# 結果を出力
print("Yes")
for w in P[2:]:
print(w)
# メイン処理
n, m, edges = io_func()
solve(n, m, edges)
###
# n: 部屋の数
# m: 通路の数
# edges: 通路の情報（各要素は [部屋A, 部屋B] の形式）
# G: グラフの隣接リスト表現
# visit: 各部屋の訪問フラグ
# D: 部屋1からの最短距離
# P: 各部屋の親（道しるべが指す部屋）
# Q: BFSで使用するキュー
# 1. io_func関数:
# - 標準入力から部屋数、通路数、通路の情報を読み取る
# 2. solve関数:
# - グラフを隣接リスト形式で構築
# - BFSのためのデータ構造を初期化
# - BFSを実行し、各部屋の最短経路と親を記録
# - 結果を出力（"Yes"と各部屋の道しるべ）
# 3. メイン処理:
# - io_func関数を呼び出してデータを取得
# - solve関数を呼び出して問題を解決```