ABC282_D – Make Bipartite 2

問題
提出
1. 3回目くらいで解けた

問題

D - Make Bipartite 2

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

提出

Submission #45082701 - HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282)

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

3回目くらいで解けた

以下、解法を書く。

$(全ての頂点の組み合わせの数)-(同じ色同士の組み合わせの数)-(存在する辺の数)$を使って解く。

グラフが連結の時を考える。
グラフGが二部グラフでない時、辺を追加しても二部グラフにすることはできない。
グラフGが二部グラフかつ辺を追加して得られるグラフも二部グラフの時、追加できる辺の数は$(全ての頂点の組み合わせの数)-(同じ色同士の組み合わせの数)$となる。
さらに元々あった辺の数を引くと、追加できる辺の数になる。

グラフが非連結の時を考える。
非連結グラフは(頂点が1の場合も含めて)いくつかの連結グラフでできている。
この連結グラフ同士の関係を考えてみる。
連結グラフが一つでも二部グラフでない場合は、どんな辺を追加しても二部グラフにはできない。
全ての連結グラフが二部グラフの場合を考える。
ある二部グラフ$G_1$ともう一方の二部グラフ$G_2$とする。
この時、$G_1$の任意の頂点から$G_2$の任意の頂点へ線を追加できる。
つまり、$G_1,G_2$のうち、線を追加して二部グラフにならないのは、$G_1$内の同じ色同士、$G_2$内の同じ色同士になる。

全てのグラフの頂点を$N$、辺がM本、連結なグラフがK個あるとして、白の数を$W_1,W_2…W_K$、黒の数を$B_1,B_2…B_K$とすると、答えは以下のようになる。
$N*(N-1)/2 – \sum_{i=1}^{K}W_i*(W_i-1)/2 – \sum_{i=1}^{K}B_i*(B_i-1)/2 – M$