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