辺の追加 Ruby編（paizaランク B 相当）

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

問題

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

巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路 (巡回路) のうち最も短いものを求める問題です。

ここでは、巡回セールスマン問題に対する貪欲法を学習しましょう。このアルゴリズムは発見的解法 (ヒューリスティクス) と呼ばれるもので、ある程度良い解が出力されることが期待されるものの、解の精度は全く保証されません。

巡回セールスマン問題に対する貪欲法の概要は、以下の通りです。

・ 都市を頂点とし、辺を 1 本も含まないグラフ G を用意する
・ 都市のペアを結ぶ辺を全て列挙し、E とする
・ E が空になるまで、以下を繰り返す
    ・ E に含まれる辺のうち最も長さが短いものを E から削除して e とする
    ・ G に e を追加したグラフを G' とする。G' のすべての頂点の次数が 2 以下かつ G' に閉路が存在しないなら、G を G' で更新する
・ この時点で G は全都市を結ぶ一本のパスになっている (次数 1 の都市がただ 2 つ存在する) ため、その始点と終点を辺で繋いで巡回路を作る

ここでは、この貪欲法を実装する前準備として、G' のすべての頂点の次数が 2 以下かつ G' に閉路が存在しないかどうかを判定する練習をしましょう。

n 個の都市 (都市 0、都市 1、...、都市 n-1) と、都市と都市を結ぶ m 本の辺からなるグラフ G が与えられます。このグラフ G は、すべての都市の次数が 2 以下で、閉路を含んでいません。グラフ G に含まれない辺 e が与えられます。G に e を追加したグラフ G' について、G' のすべての都市の次数が 2 以下かつ G' に閉路が存在しないかどうかを判定してください。

なお、各都市は二次元平面上の点として与えられます。

入力される値

n m
a_0 b_0
a_1 b_1
...
a_{m-1} b_{m-1}
ea eb

・ 1 行目に、都市の個数 n と辺の本数 m が与えられます。
・ 2 行目から、m 行にわたりグラフ G の辺が結ぶ都市の番号のペアが与えられます。
・ m+2 行目に、辺 e が結ぶ都市の番号のペアが与えられます。

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

期待する出力: G に e を追加したグラフ G' について、G' のすべての都市の次数が 2 以下かつ G' に閉路が存在しないならばYesと、そうでないならNoと出力してください。

条件: すべてのテストケースにおいて、以下の条件をみたします。
・入力はすべて整数
・ 4 ≦ n ≦ 3,000
・ 1 ≦ m < n-1
・ 0 ≦ a_i, b_i ≦ n-1 (0 ≦ i ≦ m-1)
・ a_i ≠ b_i (0 ≦ i ≦ m-1)
・ i ≠ j ならば (a_i, b_i) ≠ (a_j, b_j)
・ 0 ≦ ea, eb ≦ n-1
・ (ea, eb) ≠ (a_i, b_i) (0 ≦ i ≦ m-1)
・ n 個の都市と辺 (a_0, b_0), ... , (a_{m-1}, b_{m-1}) からなるグラフについて、すべての頂点の次数が 2 以下かつ閉路を含まない

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

出力例1: No

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

出力例2: Yes

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

出力例3: No

問題一覧へ戻る