グラフのウォーク 2 PHP編（paizaランク C 相当）

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

問題

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

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

隣接リストとある頂点 s と自然数 k が与えられます。このとき、頂点 s から k 回移動する経路（ウォーク）を全て出力してください。ただし、ここでウォークとは頂点と枝の反復を許す経路のことを言います。

次のような再帰関数を実装して深さ優先探索を行うことで、全てのウォークを調べることができます。

dfs(v, walk, k){ // v = 現在地（現在の頂点）、walk = ウォークで訪れる頂点を順に並べた配列、k = 残りの移動回数
  k = 0 ならば{
    用意しておいた配列に、walk を追加する
  k = 0 でないならば
    v の全ての隣接頂点 i に対して{
      walk の末尾に i を追加する
      dfs(i, walk, k-1)
      walk の末尾の頂点 i を削除する
    }
  }
}

入力される値

n s k
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 と移動回数を表す自然数 k が与えられます。

・ 2i 行目には頂点 i に隣接している頂点の個数が与えられ、 2i+1 行目には頂点 i に隣接している頂点の番号が半角スペース区切りで与えられます。(1 ≦ i ≦ n)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 1 行目にウォークの総数を出力してください。その後改行して、頂点 s から k 回移動するウォークで辿った頂点の番号を順番に左から半角スペース区切りで、それぞれ改行して出力してください。2 行目以降に出力するウォークの順番は問いません。各ウォークは一番左が s であり、頂点の数は s を合わせて k+1 個になります。全てのウォークが W 個ならば、1 行目に W と出力し、その後 W 行出力してください。

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

・ 3 ≦ n ≦ 12

・ 1 ≦ s ≦ n

・ 1 ≦ k ≦ 5

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

入力例1: 4 2 4
1
2
3
1 3 4
2
2 4
2
2 3

出力例1: 25
2 1 2 1 2
2 1 2 3 2
2 1 2 3 4
2 1 2 4 2
2 1 2 4 3
2 3 2 1 2
2 3 2 3 2
2 3 2 3 4
2 3 2 4 2
2 3 2 4 3
2 3 4 2 1
2 3 4 2 3
2 3 4 2 4
2 3 4 3 2
2 3 4 3 4
2 4 2 1 2
2 4 2 3 2
2 4 2 3 4
2 4 2 4 2
2 4 2 4 3
2 4 3 2 1
2 4 3 2 3
2 4 3 2 4
2 4 3 4 2
2 4 3 4 3

入力例2: 5 5 3
2
2 5
3
1 3 5
3
2 4 5
2
3 5
4
1 2 3 4

出力例2: 32
5 1 2 1
5 1 2 3
5 1 2 5
5 1 5 1
5 1 5 2
5 1 5 3
5 1 5 4
5 2 1 2
5 2 1 5
5 2 3 2
5 2 3 4
5 2 3 5
5 2 5 1
5 2 5 2
5 2 5 3
5 2 5 4
5 3 2 1
5 3 2 3
5 3 2 5
5 3 4 3
5 3 4 5
5 3 5 1
5 3 5 2
5 3 5 3
5 3 5 4
5 4 3 2
5 4 3 4
5 4 3 5
5 4 5 1
5 4 5 2
5 4 5 3
5 4 5 4

問題一覧へ戻る