グラフの s,t パス (paizaランク B 相当)

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

問題

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

1, ..., n の番号がついた n 個の頂点とそれらをつなぐ枝からなる無向グラフを考えます。ただし、自己ループと多重辺は考えません。

隣接リストとある頂点の組 (s,t) が与えられます。このとき、頂点 s と頂点 t を端点とするパスのうち、頂点数が最も少ないものを 1 つ出力してください。複数ある場合はそのうちのどれか 1 つを出力してください。ただし、ここでパスとは頂点と枝の反復を許さない経路のことを言います。

s から t までのパスは、

今いる頂点の隣接頂点の中から訪問済みではない隣接頂点を選んで、その頂点に移動して訪問済みにする

という操作を s から始めて、 t に到着するまで繰り返すことで求めることができます。これは再帰関数を用いて実装できます。再帰関数とは、プログラムの中で自分自身の関数を呼び出す関数のことです。次のこの問題における再帰関数の基本的な処理の流れを参考にして、問題を解いてみましょう。

dfs(v, path){ // v = 現在地（現在の頂点）、path = パスで訪れる頂点を順に並べた配列
  v の全ての隣接頂点 i に対して{
    i が未訪問ならば{
      path の末尾に i を追加する
      i = t ならば{
        用意しておいた配列に path を記録する
      }
      i = t でないならば{
        dfs(i, path)
      }
      path の末尾の頂点 i を削除する
    }
  }
}

path に頂点が含まれているかどうかで、その頂点が訪問済みかどうかを判断することができます。

入力される値

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 となります。

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

・ 3 ≦ n ≦ 12

・ 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 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 3

問題一覧へ戻る