閉路の判定 R(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
1, ..., n の番号のついた n 個の頂点とそれらをつなぐ枝からなる無向グラフを考えます。ただし、自己ループと多重辺は考えません。
m 本の枝が与えられます。この m 本の枝から構成される、閉路が存在しない無向グラフ G に枝 (c_j, d_j) (1 ≦ j ≦ q) を追加したグラフを G_j とします。G_j に閉路が存在するかどうか判定してください。G_j は、G に枝 (c_j, d_j) の 1 本のみを追加したグラフであり、G_{j-1} に枝 (c_j, d_j) を追加したグラフではないことに注意してください。
- 入力される値
-
n m q
a_1 b_1
...
a_m b_m
c_1 d_1
...
c_q d_q
・ 1 行目に、頂点の個数を表す n、枝の本数を表す m、調べるグラフの数を表す q が与えられます。
・ i + 1 行目に、グラフ G を構成する枝 i を表す頂点の組 (a_i, b_i) が与えられます。(1 ≦ i ≦ m)
・ j + m + 1 行目に、グラフ G_j を構成する枝 j を表す頂点の組 (c_j, d_j) が与えられます。(1 ≦ j ≦ q)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
合計 q 行出力してください。j 行目に、グラフ G_j に閉路が存在するなら
Yes、そうでなければNoと出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 2 ≦ n ≦ 100
・ 1 ≦ m ≦ n-1
・ 1 ≦ q ≦ n(n-1) / 2 - m
・ 1 ≦ a_i, b_i ≦ n (1 ≦ i ≦ m)
・ a_i ≠ b_i (1 ≦ i ≦ m)
・ 1 ≦ c_j, d_j ≦ n (1 ≦ j ≦ q)
・ c_j ≠ d_j (1 ≦ j ≦ q)
・ 同じ頂点の組は 2 回以上入力されない
・ グラフ G には閉路は存在しない
- 入力例1
-
6 4 5
1 6
1 2
1 4
1 5
3 4
4 6
5 6
2 5
3 5
- 出力例1
-
No
Yes
Yes
Yes
No
- 入力例2
-
8 7 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
2 8
4 6
5 7
- 出力例2
-
Yes
Yes
Yes
