1. paizaラーニングトップ
  2. レベルアップ問題集
  3. 幅優先探索・深さ優先探索メニュー(言語選択)
  4. 問題一覧
  5. 木の深さ優先探索

幅優先探索・深さ優先探索メニューのサムネイル
木の深さ優先探索(paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

木を構成する 1 〜 N の番号がつけられた頂点とそれらを結ぶ辺の情報と、頂点番号 X が与えられるので、頂点 X から次のルールにしたがって深さ優先探索をしたときに訪れる頂点番号を順に出力してください。

・現在の頂点に隣接している頂点のうち、未訪問かつ番号が一番小さい頂点を探索する。

入力される値

N X
a_1 b_1
...
a_{N-1} b_{N-1}


・ 1 行目では、頂点の数 N と、頂点番号 X が半角スペース区切りで与えられます。
・ 続く N-1 行では、N-1 個の辺の両端の頂点の番号 a_i, b_i (1 ≦ i ≦ N-1) が与えられます。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

・与えられた木を頂点 X から深さ優先探索をしたときに訪れる頂点の番号を順に改行区切りで出力してください。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N ≦ 200
・1 ≦ X ≦ N
・1 ≦ a_i, b_i ≦ N (1 ≦ i ≦ N-1)
・a_i ≠ b_i (1 ≦ i ≦ N-1)

入力例1

5 2
1 2
1 3
2 4
4 5

出力例1

2
1
3
4
5

問題一覧へ戻る

ページの先頭へ戻る