2部グラフ判定問題 - 30歳で競プロに目覚めた霊長類のブログ

先日のコドフェで、2部グラフってのを扱う問題が出たので、勉強してみた。

2部グラフとは

(雑な説明、ご容赦ください)
いくつかの頂点があって、それらを辺で繋いで考えるモデルをグラフという。
棒グラフとか、円グラフとか、折れ線グラフとかのグラフではなくて、「グラフ理論」のはなし。

グラフ理論のグラフにも種類があって、2部グラフはその中の1つ。
どんな特徴があるかというと、頂点を2つのチームに分けたとき、「全ての辺が、自分チームと相手チームを結んでいる」ように分けることができる。

2部グラフの例
2部グラフじゃない例

例えば、男女の複雑な三角関係や四角関係(!?) を図に書いたとき、男女間でしか線が引かれていなければ2部グラフと言える。
男男間、女女間にも線が引かれていれば、2部グラフじゃないかもしれない。
かもしれないと言ったのは、別の何かしらの基準で(例えば右利きの人と左利きの人みたいに)チーム分けしたときに、「全ての辺が、自分チームと相手チームを結んでいる」ふうにできれば、2部グラフだから。

よく考えたら、三角関係が含まれていたら、2部グラフになり得ないっすね。^^;

2部グラフ判定問題の解き方

2部グラフ判定問題とは、与えられたグラフが2部グラフかどうか、という問題である。
「蟻本」の94ページに、C++のコードが載っていたので、意訳してpythonで書いてみた。

全ての辺において、一方が黒、もう一方が白となるように頂点を塗ることを考える。
2部グラフの場合、ある頂点の色が黒だとすると、そこに隣接している頂点は一意に白と決まる。
最初は適当に1箇所を黒で塗って、あとはDFS(深さ優先探索)で白、黒、白... とどんどん塗っていって、矛盾がなければ2部グラフ。

難しそうに思えて、意外と単純！

# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)

# 入力のつもり。esはよくある隣接リストで辺を表したもの。
N = 5
#es = [[1,2,3],[0,2],[0,1],[0,4],[3]] # False
es = [[1,3],[0,2],[1,3],[0,2,4],[3]] # True

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)] 

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

print(is_bipartite())

ちなみに、2部グラフは英語では、bipartite graph というみたい。
biは"2"、partiteは "partに分ける"ってことかな？(適当)
is_nibu() とかでもいいんだけど、なんかダサかったので(笑)

おまけで、再帰なし版も載せておきます。

# 入力のつもり。esはよくある隣接リストで辺を表したもの。
N = 5
#es = [[1,2,3],[0,2],[0,1],[0,4],[3]] # False
es = [[1,3],[0,2],[1,3],[0,2,4],[3]] # True

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    stack = [(0,1)] # (頂点、色)のタプルをスタックする。最初は(頂点0, 黒(1))
    while stack:
        #スタックから最後に追加された(頂点, 色)をpop
        v,color = stack.pop()
        #今いる点を着色
        colors[v] = color
        #今の頂点から行けるところをチェック
        for to in es[v]:
            #同じ色が隣接してしまったらFalse
            if colors[to] == color:
                 return False
            #未着色の頂点があったら反転した色と共にスタックに積む
            if colors[to] == 0:
                 stack.append((to, -color))
    #調べ終わったら矛盾がないのでTrue
    return True

print(is_bipartite())

DFSを初めて覚えたとき、再帰なしのコードで覚えたので、こっちのほうが個人的に馴染みがある。
再帰は深さとか気にしなきゃいけないし、動きをイメージしづらいし、デバッグしづらい、って意識があって、あんまり書きたくないと思ってた。
でもこうやって比較すると、なるほどこのDFSだと再帰のほうがコードがすっきりしてる。
(イメージのしづらさとかは置いといて)
引き出しは多いほうがいいから、両方書けるようになっておこうっと。

実践例

さて、これでようやく、先日のコドフェ予選BのC問題が解けるようになりました。
問題はこちらです。
C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder

(意訳)
N <= 10⁶ 頂点を、M <= 10⁶ の辺で結んでいる。
連結な無向グラフで、自己辺や多重ループはない。
3つの辺を経由してたどり着ける(＝あいだに2頂点を経由する)2点を全て結ぶように辺を追加するとき、最大で何本の辺を追加できるか。

これ、解く方針がわかりませんでした。
N,M <= 10⁶ のサイズがネックで、私の思いつく解法だとどうしても間に合わない。
(全ての頂点から伸びてる辺、のそのまた先の伸びてる辺、を調べるだけで、 O(NM) ぐらい？にはなってしまう気がした。)
小手先の工夫でゴリゴリやって倒せる相手じゃなかった。

解説を見たら、魔法みたいな解法がありました！
どうも、探索で解くというよりは、グラフの性質を使って解く模様。
より詳しくは、解説を見てね。~~(私レベルには若干わかりづらい)~~

まず、距離が3辺離れた点を繫ぐということは、距離3が1になり、
同様に距離が奇数離れた点の間は2ずつ縮めることができて、そのうち辺を繋げる！
なるほどなぁ。。気づかなかった。。

そして、ここで、2部グラフが登場する。
2部グラフの場合、自分チームと相手チームを結んでいる辺しか存在しない。
どの頂点からも、奇数個の辺をたどって行ける頂点は相手チームで、偶数個の辺をたどって行ける頂点は自分チーム。
もちろん1辺の両端は異なるチームだし、3辺離れた頂点同士も、異なるチームになる。
とすると、この問題のルールにおいては、同じチーム同士はどうやっても結べない！

反対に、2部グラフでなければ、どこかしらの2点間は
奇数個の辺をたどっていくルートと、偶数個の辺をたどっていくルートが存在する
ということだから、全ての辺は、いずれ繋ぐことができる！

なので、結論は

2部グラフなら、黒・白と塗った頂点数をB,Wとして、B*W - M本。
2部グラフでなければ、全頂点間が結ばれるので、 N(N-1)//2 - M本。

になるらしい。
すっごーい　！！

早速、上で書いたコードをぺたりと貼り付けて、ACもらってきました！

import sys
sys.setrecursionlimit(10**7)
 
N,M = map(int,raw_input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,raw_input().split())
    a,b = a-1,b-1
        es[a].append(b)
        es[b].append(a)
 
colors = [0 for i in range(N)]
 
def dfs(v,color):
    colors[v] = color
    for to in es[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
 
if is_bipartite():
    b = (sum(colors) + N) // 2
    w = N-b
    print(b*w - M)
else:
    all = N*(N-1) // 2
    print(all - M)

なお、2部グラフ判定のところ、再帰版ではAC取れたけど、
再帰なし版もsubmitしたら、テストケースが1つTLEだった。
ステップ数はさほど変わらないような気がするが、、ナゼだ。。
どなたか分かる方、ご教授ください。。。(考察放棄)

この問題のキモ

この問題、見抜かなきゃいけないことがたくさんありました。

N,M <= 10⁶ のサイズは、工夫したところで、隣の隣の、、みたいな探索は到底できないこと。
グラフの性質を使って計算で解く問題ということ。
奇数個離れた頂点なら、いずれ、全て結ぶことができること。
2部グラフかどうかで答えの方針が変わること。

2部グラフを知っていなきゃ解けない問題だったのだけど、
知らなかったとしても、3番目のポイントまで見抜いていなければ、どのみち解けなかったという。

ぐぬぬ。
精進します！