ABC282-D : Make Bipartite 2 解説

ABCのD問題が久しぶりに解けなかったので解説しながら理解を深めます．

atcoder.jp

問題概要

• 単純無向グラフG(V, E)が与えられます．u < vを満たす頂点(u, v)の組で次の2つを満たす組の総数を出力してください．

  • 頂点uと頂点vを結ぶ辺は存在しない．
  • Gに辺(u, v)を追加したとき，Gは二部グラフである．

• 制約 : 1 ≦ |V| ≦ 2 × 10⁵, 0 ≦ |E| ≦ min(2 × 10⁵, |V| × (|V| - 1)/2)

考察ステップ

• 制約からO(|V|^2)が通らないので全探索は当然×
• そもそも入力グラフが二部グラフでなければ辺追加しても二部グラフではないため，0になりそう
• 解の候補全体から辺を追加した時に制約を満たさない組を引いた方が良さそう

コード

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

こうなりました

やること

1. グラフを連結成分ごとに分割する
2. それぞれの分割したグラフについて，二部グラフとなるように2彩色する
3. 解候補全体からそれぞれの分割したグラフの同じ色の頂点からなる組合せの数を引いたものが答え

1. グラフを連結成分ごとに分割する

• UnionFindを使うと便利です．
  • 特にAtCoder Libraryを用いるとgroupsという関数が用意されていて，各連結成分に含まれる頂点まで教えてくれるので良いです．
• 提出コードでは，得られた連結成分の情報から実際にグラフを分割しています．サイズが連結成分の数の連結グラフの配列にしてます．

2. 2採色する

• 幅優先探索を用いて1つの頂点の色を決め打って色を塗ります．
  • この時，同じ色の頂点同士は辺を持ってはならないです．
  • どうしてもそのような頂点が生まれる場合，そのグラフは二部グラフではありませんので，0を出力して終了します．
  • 詳しくは二部グラフの判定について学ぶと良いと思います．
• 同じ色の頂点を1つのグループとすると，二部グラフになります．

3. 答えを求める

• ある二部グラフにおいて，1つの辺を追加して二部グラフとなる条件は，違う色の2つの頂点を結んだ場合です．
• 上の例では，辺(1, 4)や辺(1,5) は追加できますが，辺(1, 2)は追加できません．
• そのような数を考えると，1つの二部グラフが与えられた時のこの問題は，頂点数をN，辺の数をM，それぞれの色で塗られた頂点の数をS, Tとすると，次のようになります．

• それでは2つ以上の二部グラフからなって，双方から1つの頂点を選び辺を作る場合はどのようになるでしょうか．
• 実はどのような選び方でも問題なく二部グラフとなります．

• このことから，答えは頂点数をN，辺の数をM，連結成分の数をW, Gの連結な部分グラフG_iにおいてそれぞれの色で塗られた頂点の数をS_i, T_iとすると，次のようになります．