1 頂点の移動
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
木を構成する 1 〜 N の番号がつけられた頂点とそれらを結ぶ辺の情報と頂点番号 X, Y が与えられます。
頂点 X から次のルールにしたがって幅優先探索と深さ優先探索をしたとき、頂点 Y を訪れるまでに注目する未訪問の頂点の数が少なくなるのはどちらの探索かを調べてください。
幅優先探索
・現在の頂点に隣接している全ての未訪問の頂点を、番号が一番小さい頂点から順に探索する。
深さ優先探索
・現在の頂点に隣接している頂点のうち、未訪問かつ番号が一番小さい頂点を探索する。
- 入力される値
-
N X Y
a_1 b_1
...
a_{N-1} b_{N-1}
・ 1 行目では、頂点の数 N と、頂点番号 X, Y が半角スペース区切りで与えられます。
・ 続く N-1 行では、N-1 個の辺の両端の頂点の番号 a_i, b_i (1 ≦ i ≦ N-1) が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
頂点 X から幅優先探索と深さ優先探索をしたとき、
・幅優先探索が先に頂点 Y を訪れる場合 "bfs" を出力してください。
・深さ優先探索が先に頂点 Y を訪れる場合 "dfs" を出力してください。
・2 つの探索が同時に頂点 Y を訪れる場合 "same" を出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 200
・1 ≦ X, Y ≦ N
・1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ N-1)
・a_i ≠ b_i (1 ≦ i ≦ N-1)
- 入力例1
-
6 1 5
1 2
1 3
1 4
2 5
3 6
- 出力例1
-
dfs
