問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
木についての情報と頂点番号 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}
・A から距離が X の全ての頂点の番号を昇順に改行区切りで出力してください。
・そのような頂点が存在しない場合は改行のみを出力してください。
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 100
・1 ≦ A ≦ N
・1 ≦ X ≦ N-1
・1 ≦ a_i , b_i ≦ N (1 ≦ i ≦ N-1)
6 1 2
1 2
1 3
2 4
4 5
4 6
4
10 10 4
8 4
8 3
1 6
5 3
2 8
10 3
5 7
1 9
1 5
6
9