距離が X の頂点
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
木についての情報と頂点番号 A と整数 X が与えられるので、A から距離が X の全ての頂点の番号を昇順で出力してください。
全ての頂点について A からの距離を求めるには A から幅優先探索を行えば良いです。幅優先探索の方針は次の通りです。
頂点数を N とする。頂点 A からの距離を保持するための配列 len[N] と、幅優先探索のためのキュー Q を宣言する。
len[A] = 0 とする
Q に A を追加する
Q が空になるまで繰り返し{
Q の先頭の値を取り出して A とする
A に隣接した頂点のうち、未訪問（距離が確定していない頂点）の距離を A の len[A] + 1 とし、その頂点を Q に追加する。
}
- 入力される値
-
N A X
a_1 b_1
...
a_{N-1} b_{N-1}
・1 行目には、頂点の数 N, 頂点番号 A, 整数 X が与えられます。
・続く N-1 行では、各辺の両端の頂点 a_i , b_i が与えられます。(1 ≦ i ≦ N-1)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・A から距離が X の全ての頂点の番号を昇順に改行区切りで出力してください。
・そのような頂点が存在しない場合は改行のみを出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 100
・1 ≦ A ≦ N
・1 ≦ X ≦ N-1
・1 ≦ a_i , b_i ≦ N (1 ≦ i ≦ N-1)
- 入力例1
-
6 1 2
1 2
1 3
2 4
4 5
4 6
- 出力例1
-
4
- 入力例2
-
10 10 4
8 4
8 3
1 6
5 3
2 8
10 3
5 7
1 9
1 5
- 出力例2
-
6
9
