✏️
ABC282 D - Make Bipartite 2 の解説の解説
二部グラフ
定義
頂点を二つの色で表し、同じ色同士を結ぶ辺が存在しないグラフ
確認方法
詳細はアルゴ式を見よう
- ある頂点を0、接続している頂点を1、次に接続しているものを0…として頂点の色(数字)を決める
- すべての辺が、頂点色0と1を結ぶ辺であることを確認する
-
全頂点にて上記の確認を行う
独立した頂点がある場合、評価できないので全部頂点確認する必要あり
今回の問題でも頂点0でのみ判定するコードだと以下のようにWAとなる
この問題の肝
二部グラフの特徴
二部グラフじゃないものに辺を足しても二部グラフには戻らない
与えられたグラフが二部グラフでなければ、解は0である
追加できる辺の数え上げ
従って計算で求める必要がある。
頂点Nでの最大の辺の数：
すでに結んでいる辺の数：
頂点0-0同士で結べる辺の数：
頂点1-1同士で結べる辺の数：
となるので、最大の数から除外したものが解である
色の塗り方
- 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