Is Graph Bipartite
グラフには n 個のノードがあり、0 から n-1 までのラベルが付いています。edges 内の各ペア [a, b] は、ノード a とノード b の間の無向辺を表します。グラフはいくつかの独立した部分に分かれている場合があり、辺をまったく持たないノードもあります。
すべての辺が一方のグループのノードともう一方のグループのノードを結ぶように、ノードを2つのグループに分けられるとき、グラフは二部グラフです。グラフが二部グラフなら true を、そうでなければ false を返してください。
関数
- ninteger
- ノードの数。0 から n-1 まで番号が付けられている
- edgesinteger-2d-array
- 無向辺。それぞれがペア [a, b] です
- 戻り値boolean
- ノードを 2 つのグループに分け、すべての辺がグループ間にある場合は true、そうでなければ false
制約
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [a, b]、0 ≤ a, b ≤ n-1かつa ≠ b- どの辺も、どちらの方向から見ても2回現れることはありません。
例
- 入力
- n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
- 出力
- true
- 説明
- ノード 0 と 2 を一方のグループに、ノード 1 と 3 をもう一方のグループに入れます。4 本の辺はそれぞれ、2 つのグループを結びます。
- 入力
- n = 3edges = [[0, 1], [1, 2], [2, 0]]
- 出力
- false
- 説明
- ノード 0 と 1 は異なるグループに属し、ノード 2 はその両方と異なるグループに属さなければなりませんが、グループは 2 つしかありません。3 本の辺からなるサイクルを分割することは決してできません。
- 入力
- n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
- 出力
- false
- 説明
- 辺
[0, 1]は問題なく分割でき、ノード 5 には辺がありませんが、ノード 2、3、4 は三角形を形成しています。失敗する部分が 1 つでもあれば、答えはfalseになります。
発展問題
グラフが二部グラフでない場合、証明として奇数長の閉路を1つ、そのノードを順番に並べて返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ノード 0 を最初のグループに入れます。その隣接ノードはそれぞれどこに入れる必要がありますか？さらに、それらの隣接ノードはどうでしょうか？
連結成分の1つの頂点を配置すると、その成分のほかのすべての頂点の配置は決まります。辺の両端は、必ず異なるグループに入ります。この強制された配置によって、ある辺の両端が同じグループに入る場合に限って、グラフは条件を満たしません。そのようなことが起こるのは、その成分に奇数長のサイクルがある場合に限ります。
幅優先探索で色を割り当てます。部分の最初のノードに色0を割り当て、色が割り当てられていない各隣接ノードには現在のノードと反対の色を割り当てます。隣接ノードがすでに同じ色なら、
falseを返します。色が割り当てられていないすべてのノードから新たに探索を開始し、どの部分も見落とさないようにします。
解説
1つのノードのグループを選ぶと、接続された部分の残りも決まります。隣接ノードはもう一方のグループに入ります。幅優先探索で2色を交互に使って各部分を彩色します。すべての辺の両端が異なる色になる場合に限り、グラフは二部グラフです。グラフは非連結の場合があるため、色が付いていない各ノードから新たに探索を始めます。
すべての分割を試す
正しいが、最大のテストでは終わらない
考え方
すべての分割を試します。各ノードのグループを1ビットとみなすと、nビットで2進数が構成され、0から2^n-1まで数えることで、すべての分割を一度ずつ調べられます。各分割についてすべての辺を確認し、すべての辺がグループをまたぐ分割があればtrueを返します。ノードが1つ増えるごとに分割数は2倍になり、ノードが20個なら約100万通りになります。
アルゴリズム
- 0 から 2^n-1 までの各数値について、ビット
iで指定されるグループにノードiを入れます。 - すべての辺が2つのグループを結んでいる場合は、
trueを返します。 - どの分割もうまくいかない場合は、
falseを返します。
def isBipartite(n, edges):
side = [0] * n # side[x] is 0 or 1: the group of node x in the current split
while True:
# Does every edge cross between the two groups?
if all(side[u] != side[v] for u, v in edges):
return True
# Move to the next split, counting in binary over side.
i = 0
while i < n and side[i] == 1:
side[i] = 0
i += 1
if i == n:
return False # all 2^n splits have been tried
side[i] = 1各ノードの近傍に対するUnion-find
考え方
ノードがどちらのグループに入っても、そのすべての隣接ノードはもう一方のグループに入るため、同じグループを共有します。各ノードについて、すべての隣接ノードを1つのunion-find集合に統合します。すると、1つの集合には同じ側に属することを強制されたノードが含まれます。両端が同じ集合にある辺は、グループ内にとどまることを強制されるため、グラフは二部グラフではありません。
この判定ですべての失敗を検出できます。奇数サイクルでは、辺を2つずつ統合すると最初のノードと最後のノードが結ばれ、閉路を完成させる辺がこの2つを結びます。奇数サイクルがなければ、各統合で結ばれる2つのノード間の距離は偶数であり、同じ側に位置します。ノードの最初の隣接ノードであるアンカーは、そのノードの隣接ノードが属する集合を表すため、隣接リストを使わずに、辺が順に処理されるたびに統合できます。サイズによる併合と経路の半分短縮を使うと、2m回の統合とm回の判定にかかるコストはO(m α(n))です。
アルゴリズム
- すべてのノードについて、
parent[x] = xとanchor[x] = -1を設定します。 - 各辺
[u, v]について、まだアンカーがない場合は、それぞれの端点のアンカーにもう一方の端点を設定します。 vをanchor[u]の集合に、uをanchor[v]の集合にマージします。- ある辺の両端点が同じ集合にある場合は
falseを返し、そうでなければtrueを返します。
def isBipartite(n, edges):
parent = list(range(n)) # every node starts as its own group
size = [1] * n
anchor = [-1] * n # the first neighbour seen for each node
def find(x):
# Walk up to the root, halving the path on the way.
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
a, b = find(a), find(b)
if a == b:
return
# Hang the smaller group under the larger one.
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
# All neighbours of a node must sit on one side: the side opposite the node.
for u, v in edges:
if anchor[u] == -1:
anchor[u] = v
if anchor[v] == -1:
anchor[v] = u
union(anchor[u], v) # v joins the other neighbours of u
union(anchor[v], u) # u joins the other neighbours of v
# An edge whose two ends were forced onto one side cannot cross.
for u, v in edges:
if find(u) == find(v):
return False
return Trueすべての部分を幅優先探索で2色に塗り分ける
考え方
矛盾があれば判定は確定です。各連結成分の最初の色は自由に選べ、それを反転すると連結成分全体の色が反転します。それ以外の色は辺によって決まります。探索では、開始点からの距離が偶数か奇数かによってノードを色分けするため、隣接する2つのノードが同じ色になるのは、その連結成分に奇数長のサイクルがある場合だけで、その場合は分割できません。
探索で調べるのはその連結成分だけなので、すべてのノードを順に見て、まだ色が付いていない各ノードから新しい探索を開始します。3つ目の例では、ノード0からの探索でノード0と1に色が付きます。ノード2からの探索では、ノード2に色0、ノード3と4に色1を付けた後、両端が色1の[3, 4]を見つけます。結果はfalseです。各ノードには1回だけ色を付けてキューに追加し、リストの2m個の要素をそれぞれ1回ずつ比較します。時間計算量と空間計算量はO(n + m)です。
アルゴリズム
- 各辺を両端の頂点の隣接リストに追加し、すべての色を -1 に設定します。
- 順番に、色が付いていない各ノードに色 0 を付けて、キューに入れます。
- ノードを取り出します。色が付いていない各隣接ノードに反対の色を付けてキューに入れます。隣接ノードが同じ色の場合は、
falseを返します。 - すべての連結成分に色が付いたら、
trueを返します。
from collections import deque
def isBipartite(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
color = [-1] * n # -1: not colored yet, otherwise 0 or 1
for start in range(n):
if color[start] != -1:
continue
# A new component: its first node can take either color.
color[start] = 0
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if color[nxt] == -1:
# A neighbour must take the other color.
color[nxt] = 1 - color[node]
queue.append(nxt)
elif color[nxt] == color[node]:
return False # this edge stays inside one group
return True
落とし穴と境界ケース
- ノード 0 からのみ探索する。3つ目の例はノード 0 の周辺では問題ないが、ノード 2、3、4 の間では失敗する。
- 各辺を一方のリストにしか追加しない。辺
[1, 0]と[2, 0]があると、ノード 0 は色 0 になり、隣接ノードが見えない。その後、ノード 1 も色 0 になり、ノード 0 への辺が色の衝突のように見えるが、経路の分割自体は問題ない。 - ノードをキューから取り出したときに色を付ける。すると、ノードがキューに2回入ることがあり、2回目の訪問で最初の色が上書きされる。キューに追加するときに色を付ける。
- 二部グラフと非巡回グラフを混同する。正方形にはサイクルがあるが二部グラフであり、分割を妨げるのは奇数長のサイクルだけ。
よくある質問3
Is Graph Bipartite の時間計算量はどれくらいですか？
幅優先または深さ優先で色を塗る方法は、m 本の辺に対して O(n + m) で実行されます。各ノードは一度色付けされ、各辺は両端から一度ずつ比較されます。隣接リストと色が使用する領域は O(n + m) です。Union-find でも O(n + m α(n)) で同じ答えが得られます。
なぜ奇数長の閉路があるとグラフは二部グラフではなくなるのですか？
サイクルに沿って進むと、グループは交互になります。つまり、第1、第2、第1、第2です。辺の数が奇数のサイクルでは、奇数回切り替えた後に出発点へ戻るため、出発点は両方のグループに属することになってしまいます。グラフが二部グラフであるのは、奇数長のサイクルを持たない場合に限ります。
グラフが二部グラフかどうかを判定するには、BFSとDFSのどちらを使うべきですか？
どちらでも問題ありません。色付けのルールは同じで、訪問順序だけが変わります。大きなグラフでは、再帰版だとノードごとに1回ずつ呼び出しが深くなる可能性があるため、明示的なスタックを使ってDFSを書きましょう。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isBipartite(n, edges):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
n = 4 edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
期待される出力
true