✏️

ABC282 D - Make Bipartite 2 の解説の解説

2022/12/18に公開約2,200字

https://atcoder.jp/contests/abc282/tasks/abc282_d

二部グラフ

定義

頂点を二つの色で表し、同じ色同士を結ぶ辺が存在しないグラフ

確認方法

https://algo-method.com/tasks/962/editorial
詳細はアルゴ式を見よう

  • ある頂点を0、接続している頂点を1、次に接続しているものを0…として頂点の色(数字)を決める
  • すべての辺が、頂点色0と1を結ぶ辺であることを確認する
  • 全頂点にて上記の確認を行う
    独立した頂点がある場合、評価できないので全部頂点確認する必要あり
    今回の問題でも頂点0でのみ判定するコードだと以下のようにWAとなる

https://atcoder.jp/contests/abc282/submissions/37367825

この問題の肝

二部グラフの特徴

二部グラフじゃないものに辺を足しても二部グラフには戻らない
与えられたグラフが二部グラフでなければ、解は0である

追加できる辺の数え上げ

N=2*10^5となっていることから、辺の数を総当りで数えるとO(N^2)となりTLE
従って計算で求める必要がある。

頂点Nでの最大の辺の数:N\times(N-1)/2
すでに結んでいる辺の数:M
頂点0-0同士で結べる辺の数:頂点0の個数 \times (頂点0の個数-1) /2
頂点1-1同士で結べる辺の数:頂点1の個数 \times (頂点1の個数-1) /2
となるので、最大の数から除外したものが解である

色の塗り方

  • BFSで上手いこと塗れるが、どちらの頂点か数え上げるのはちょっと大変
  • 頂点の色0と1の数え上げのコツ
    • 0、1の反転ではXOR(^)を使うとわかりやすいコードになる
    • cnt[0の頂点の数,1の頂点の数]という配列を作るとわかりやすいコードになる
    • 開始地点の頂点を数え忘れない様、初期値に入れる
コメント付きのACコード例
# template
from math import gcd
from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
# mod = 10 ** 9 + 7
# mod = 998244353

n, m = mi()
edges = [li() for i in range(m)]
g = defaultdict(list)
for u, v in edges:
    g[u - 1].append(v - 1)
    g[v - 1].append(u - 1)
# 頂点の色、0か1かを埋める
col = [-1] * n
res = n * (n - 1) // 2 - m
# 2部グラフ判定
is_bipartie = True

# BFS 
for i in range(n):
    if col[i] != -1:
        continue
    col[i] = 0
    que = [i]
    cnt = [1, 0]
    while que:
        q = que.pop()
        for num in g[q]:
            # 色を塗ってなかったら、今の色を反転させて塗りキューに加える
            if col[num] == -1:
                col[num] = col[q] ^ 1
                que.append(num)
                # 塗った色で数え上げる
                cnt[col[num]] += 1
            # 同じ色同士で接続しているか
            # 接続していれば2部グラフではない    
            if col[num] == col[q]:
                is_bipartite = False
    # 同じ色同士の頂点は結べないので、
    # 結べない線の数を数えて答えから引く
    res -= cnt[0] * (cnt[0] - 1) // 2
    res -= cnt[1] * (cnt[1] - 1) // 2
# 2部グラフなら答えを出力
if is_bipartite:
    print(res)
else:
    print(0)

チラシの裏

  • 辺の数が計算できると思いつけなかったのがくやちい
  • 頂点の数え上げ方と、01反転方法のコードの簡潔な書き方が勉強になった
    上位陣が何気なく書いているコードには叡智が詰まってるなぁ
    叡智が過ぎて俺にはまだ早いな、となることもそれなりにあるけれども

Discussion

ログインするとコメントできます