問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

単純無向グラフ $G=(V,E)$ が与えられる. ただし,

$V:=\{1,2, \dots, N\}$
$E:=\{u_j v_j \mid j=1,2, \dots, M\}$

である. $1 \leq u \lt v \leq N$ である整数の組 $(u,v)$ のうち, 次の条件を満たす組の数を求めよ.

$uv \not \in E$
$G+uv$ は二部グラフである.

制約

$2 \leq N \leq 2 \times 10^5$
$0 \leq M \leq \min \left(2 \times 10^5, \dfrac{N(N-1)}{2} \right)$
$1 \leq u_j, v_j \leq N$
$G$ は単純

解法

二部グラフの部分グラフも二部グラフである. よって, この対偶より, 二部グラフではないグラフの拡大グラフも二部グラフではない. よって, $G$ 自身がが二部でない場合はどのように辺を追加しても二部グラフとなることは無いので, 答えは $0$ である.

以降では $G$ は二部グラフであるとする. このとき, $G$ の連結成分を $K$ とし, $k$ 番目の連結成分における部集合を $X_k, Y_k$ とする.

このとき, $X_1, Y_1, \dots, X_K, Y_K$ は頂点集合 $V$ の分割になっている. よって, 各 $v \in V$ に対して, $v \in A$ となるような $A \in \{X_1, Y_1, \dots, X_K, Y_K\}$ が唯一存在する. この $A$ を $\varphi(v)$ と書くことにする.

このとき, $uv \not \in E$ となる $u,v \in V$ に対して, この $u,v$ が条件を満たすことと, $\varphi(u) \neq \varphi(v)$ であることは同値である. 実際,

$\varphi(u) \neq \varphi(v)$ かつ, $\varphi(u), \varphi(v)$ が同じ連結成分ではないとき, 異なる連結成分間を1辺だけ結んでも二部グラフであることは保たれる.
$\varphi(u) \neq \varphi(v)$ かつ, $\varphi(u), \varphi(v)$ が同じ連結成分であるとき, $\varphi(u), \varphi(v)$ は異なる部集合であるから, 辺 $uv$ を加えても二部グラフである.
$\varphi(u)=\varphi(v)$ であるとき, 辺 $uv$ を結ぶと, 二部グラフではなくなってしまう.