二分グラフ判定

問題

頂点数 $n$ の無向グラフがあります。

隣接している頂点同士が違う色になるように、頂点に色を塗っていきます。

２色以内ですべての頂点を塗ることができるかどうか判定してください。

多重辺やループはないもとのします。

[制約]
🔹$ 1 \leqq N \leqq 1000 $

解き方

この問題は、二部グラフかどうかを判定する問題として知られています。

二部グラフとは、グラフを2つの部分集合に分け、同じ部分集合に属する頂点同士は隣接しないようにできるグラフのことです。

以下の手順に従って、二部グラフかどうかを判定することができます。

１．任意の頂点を1つ選び、そこからBFS（幅優先探索）またはDFS（深さ優先探索）を行います。
２．隣接する頂点のうち、まだ色を塗っていない頂点に、異なる色を塗ります。
３．2で塗られた頂点をスタートにして、再度BFSまたはDFSを行い、色を塗っていない頂点に色を塗ります。
４．2と3を繰り返し行い、すべての頂点に色を塗ることができたら、そのグラフは二部グラフであり、2色以内で塗ることができます。
　　一方、どのようにしてもすべての頂点に色を塗ることができなければ、そのグラフは二部グラフではありません。

ソースコード

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#-------- 入力例１ ---------
n = 3            # 頂点数
# 隣接リスト
adj_list = [
    (1, 2),     # 頂点0につながっている頂点のリスト
    (0, 2),     # 頂点1につながっている頂点のリスト
    (0, 1)      # 頂点2につながっている頂点のリスト
]
#-------- 入力例２ ---------
n = 4            # 頂点数
# 隣接リスト
adj_list = [
    (1, 3),     # 頂点0につながっている頂点のリスト
    (0, 2),     # 頂点1につながっている頂点のリスト
    (1, 3),     # 頂点2につながっている頂点のリスト
    (0, 2)      # 頂点3につながっている頂点のリスト
]
#---------------------------
def is_bipartite(adj_list):
    color = [-1] * len(adj_list)
    color[0] = 0
    queue = [0]
    while queue:
        v = queue.pop(0)
        for u in adj_list[v]:
            if color[u] == -1:
                color[u] = 1 - color[v]
                queue.append(u)
            elif color[u] == color[v]:
                return False
    return True

if is_bipartite(adj_list):
    print("Yes")
else:
    print("No")

このコードでは、is_bipartite関数で、グラフが二部グラフかどうかを判定しています。

具体的には、1つ目の頂点を0番目の色で塗り、BFSで隣接する頂点に異なる色を塗っていくことで、二部グラフであるかどうかを判定しています。

二部グラフである場合は、すべての頂点に色を塗ることができるので、結果として“Yes”を出力します。

一方、二部グラフでない場合は、すべての頂点に色を塗ることができないため、結果として“No”を出力します。

[実行結果（入力例１）]

No

入力例１のグラフを塗るためには３色必要となるため、解は“No”となります。

[実行結果（入力例２）]

Yes

入力例２のグラフは、２色で塗ることができるため、解は“Yes”となります。