グラフの各連結成分が二部グラフかどうか解析するモジュールを書いた

ごり〜

こんばんは
唐突ですが、当ブログで一番アクセス数が多い記事は6年半前に書いたこちらなんですよね

prd-xxx.hateblo.jp

今でも「二部グラフ　判定」などとググっていただけるとかなり上位にヒットして、ありがたいです

二部グラフの判定が必要になることはまあまあレアなので、自分でも特にスニペット化しておらず、このコードが必要になるたびに自分でもググったりしていました

で、最近 AGC011-C (リンク先ネタバレ注意)を解くことがあって、二部グラフの判定が必要になりました。
でも、自分が昔書いたこのコードは、グラフ全体が二部グラフでないとわかったら即座にFalse を返すので、各連結成分に対して二部グラフ性を調べたいと思ったら、ちょっと書き換えないといけませんでした

なら、各連結成分が二部グラフかどうかを調べるモジュールを書けばいいじゃんと思ったので、書きました
内容は特に難しくないので都度書けば良いレベルでもあるのですが、まあいざ必要になったときに1から実装するのとすでに書いてあるのではコンテストの結果は大きく変わると思うので、将来役に立つことを期待して書きました

これを公開することはライバルの成績を上げかねない (本当か？) のですが、この記事を読んでくださった方は特別です

今回ご紹介するのは

こちらです、 Bipartite
詳しくは上記リンク先の READMEに書かれている通りなのですが、
単純無向グラフに対して、各連結成分が二部グラフかどうかを調べるモジュールです。
中身のロジックはシンプルで、全部の頂点についてdfsをします (ただし、調査済みの頂点ならばスキップします)
dfsで調べている連結成分が二部グラフと仮定して矛盾があれば二部グラフでない、矛盾がなければ二部グラフと判定します。
O(V+E) ぐらいで解析します。

使い方実例、verify

2024/04/04 大幅な速度改善をしました

AGC011-C - Squared Graph

Submission #52010921 - AtCoder Grand Contest 011

bpt = Bipartite(es)
bpt.analize()

a = len(bpt.isolated_vertiecs)
b = len(bpt.bipartite_ccs)
c = len(bpt.not_bipartite_ccs)

ans = 2*N*a - a**2
ans += 2*b*b
ans += 2*b*c
ans += c*c
print(ans)

CODE FESTIVAL 2017 qual B C - 3 Steps

Submission #52010956 - CODE FESTIVAL 2017 qual B

bpt = Bipartite(es)
bpt.analize()

if bpt.is_bipartite():
    b,w = bpt.bipartite_distribution(0)
    print(b*w - M)
else:
    print(N*(N-1)//2 - M)

第10回 アルゴリズム実技検定 過去問 O - 3-順列

Submission #52007642 - 第10回 アルゴリズム実技検定 過去問

bpt = Bipartite(es)
bpt.analize()

B = 1000
dp = set([0])
for x in range(len(bpt.bipartite_ccs)):
    b,w = bpt.bipartite_distribution(x)
    ndp = set()
    for v in dp:
        pb,pw = v//B,v%B
        if pb+b <= c1 and pw+w <= c2:
            ndp.add((pb+b)*B + pw+w)
        if pb+w <= c1 and pw+b <= c2:
            ndp.add((pb+w)*B + pw+b)
    dp |= ndp

iso = len(bpt.isolated_vertiecs)
for v in dp:
    pb,pw = v//B,v%B
    if (c1-pb) + (c2-pw) <= iso:
        exit(print('Yes'))

print('No')