SRM441Div1Medium
問題
N個の頂点と、そろぞれの頂点同士の接続関係が与えられる。全ての頂点がつながっている状態にするのに必要な操作の最小回数を求めよ。できない場合は-1を返す。
許される操作は以下である。
- 4つの頂点A,B,C,Dを選ぶ。AとB、CとDは接続されてる。
- AとBのエッジ、CとDのエッジを取り除き、AとCまたはD、BとCまたはDを接続する。
解法
グラフを構成する余分なエッジの数Rと、グラフの数Gを計算する。
上の条件を満たす時G-1が答えとなり、それ以外は-1となる。
計算量
