パスの通れない頂点 2
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
1, ..., n の番号がついた n 個の頂点とそれらをつなぐ枝からなる無向グラフを考えます。ただし、自己ループと多重辺は考えません。
隣接リストとある頂点の組 (s,t) と s,t を含まない頂点の集合 S が与えられます。このとき、頂点 s と頂点 t を端点とし、S の頂点を通らないパスを全て出力してください。ただし、ここでパスとは頂点と枝の反復を許さない経路のことを言います。
- 入力される値
-
n s t
k
s_1 ... 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 と t が与えられます。
・ 2 行目に、頂点集合 S の頂点数を表す k が与えられます。
・ 3 行目に、頂点集合 S の頂点が与えられます。
・ 2(i+1) 行目には頂点 i に隣接している頂点の個数が与えられ、 2(i+1)+1 行目には頂点 i に隣接している頂点の番号が半角スペース区切りで与えられます。(1 ≦ i ≦ n)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
1 行目にパスの総数を出力してください。その後改行して、S の頂点を通らない頂点 s と t を端点とするパスを全て求め、各パスが辿る頂点の番号を順番に左から半角スペース区切りでそれぞれ改行して出力してください。2 行目以降に出力するパスの順番は問いません。各パスは一番左が s であり、一番右が t となります。全てのパスが W 個ならば、1 行目に W と出力し、その後 W 行出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 3 ≦ n ≦ 10
・ 1 ≦ s,t ≦ n
・ s ≠ t
・ 1 ≦ k ≦ n-2
・ 1 ≦ s_j < s_{j+1} ≦ n (1 ≦ j ≦ k-1)
・ s_j ≠ s,t (1 ≦ j ≦ k)
・ 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
-
5 1 4
3
2 3 5
2
2 5
3
1 3 5
3
2 4 5
2
3 5
4
1 2 3 4
- 出力例1
-
0
- 入力例2
-
5 5 3
3
1 2 4
2
2 5
3
1 3 5
3
2 4 5
2
3 5
4
1 2 3 4
- 出力例2
-
1
5 3
- 入力例3
-
7 3 4
1
2
6
2 3 4 5 6 7
3
1 3 7
3
1 2 4
3
1 3 5
3
1 4 6
3
1 5 7
3
1 2 6
- 出力例3
-
5
3 1 4
3 1 5 4
3 1 6 5 4
3 1 7 6 5 4
3 4
