グラフの s,t トレイル
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
1, ..., n の番号がついた n 個の頂点とそれらをつなぐ枝からなる無向グラフを考えます。ただし、自己ループと多重辺は考えません。
隣接リストとある頂点の組 (s,t) が与えられます。このとき、頂点 s と頂点 t を端点とし、s, t を通過点として含まないトレイルのうち、最も頂点数の多いものを 1 つ出力してください。複数ある場合はそのうちのどれか 1 つを出力してください。ただし、ここでトレイルとは枝の反復を許さず頂点の反復を許す経路のことを言います。
s から t までのトレイルは
今いる頂点に接続されている枝の中から通過済みでない枝を選んで、その枝を辿って別の頂点に移動して辿った枝を通過済みにする
という操作を s から始めて、 t に到着するまで繰り返すことで求めることができます。これは再帰関数を用いて実装できます。次のこの問題における再帰関数の基本的な処理の流れを参考にして、問題を解いてみましょう。
dfs(v, trail, edges){ // v = 現在地（現在の頂点）、trail = トレイルで訪れる頂点を順に並べた配列、edges = 通過済みの枝の配列
v の全ての隣接頂点 i に対して{
枝 (v,i) が通過済みでないならば{
trail の末尾に i を追加する
trail に s と t が2回以上含まれていないならば{
edges に (v,i) を追加する
i = t ならば{
用意しておいた配列に trail を記録する
i = t でないならば
dfs(i, trail, edges)
}
枝 (v,i) を edges から削除する
}
trail の末尾の頂点 i を削除する
}
}
}
- 入力される値
-
n s t
v_1
a_{1,1} a_{1,2} ... a_{1,v_1}
v_2
a_{2,1} ... a_{2,v_2}
...
v_n
a_{n,1} ... a_{n,v_n}
・ 1 行目に、頂点の個数を表す整数 n と、端点の頂点番号 s と t が与えられます。
・ 2i 行目には頂点 i に隣接している頂点の個数が与えられ、 2i+1 行目には頂点 i に隣接している頂点の番号が半角スペース区切りで与えられます。(1 ≦ i ≦ n)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
頂点 s と t を端点とするトレイルのうち最も頂点数の多いものを求め、トレイルで辿った頂点の番号を順番に左から半角スペース区切りで 1 行で出力してください。最も頂点数の多いものが複数ある場合はそのうちのどれか 1 つを出力してください。一番左が s であり、一番右が t となり、その間には s と t は含まれません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 3 ≦ n ≦ 7
・ 1 ≦ s,t ≦ n
・ s ≠ t
・ 1 ≦ v_i ≦ n-1 (1 ≦ i ≦ n)
・ 1 ≦ i ≦ n について
・ v_i = 1 のとき : 1 ≦ a_{i,1} ≦ n
・ v_i > 1 のとき : 1 ≦ a_{i,j} < a_{i,j+1} ≦ n (1 ≦ j ≦ (v_i)-1)
頂点 s と頂点 t を端点とするトレイルが少なくとも1つ存在することが保証されています。
- 入力例1
-
5 1 4
2
2 5
3
1 3 5
3
2 4 5
2
3 5
4
1 2 3 4
- 出力例1
-
1 5 3 2 5 4
- 入力例2
-
5 5 3
2
2 5
3
1 3 5
3
2 4 5
2
3 5
4
1 2 3 4
- 出力例2
-
5 1 2 3
- 入力例3
-
7 6 4
6
2 3 4 5 6 7
6
1 3 4 5 6 7
6
1 2 4 5 6 7
6
1 2 3 5 6 7
6
1 2 3 4 6 7
6
1 2 3 4 5 7
6
1 2 3 4 5 6
- 出力例3
-
6 3 2 5 1 7 2 1 3 5 7 3 4
