Pythonで敵同士が同じグループに入らないよう2グループに分けられるか判定するプログラム

人数 n と2次元配列 enemies が与えられているとします。n は [0, n - 1] のラベルが付けられた n 人の人を表し、enemies の各行は [a, b] という形式で、a と b が敵同士であることを意味します。このとき、n 人を2つのグループに分けて、敵同士が同じグループに含まれないようにできるかどうかを判定する必要があります。

たとえば、入力が n = 4、enemies = [[0, 3],[3, 2]] の場合、出力は True になります。これは [0, 1, 2] と [3] という2つのグループに分ければ、どのグループにも敵同士が存在しないようにできるためです。

この問題の考え方

この問題は、グラフ理論における二部グラフ判定として捉えることができます。人を頂点、敵関係を辺としたグラフを構築し、隣り合う頂点が異なる色になるよう塗り分け（2色配色）ができるかをDFS（深さ優先探索）で確認します。

解法の手順

• graph : 空の隣接リストを用意する

• enemies 内の敵ペア (u, v) ごとに次を行う

  • graph[u] の末尾に v を追加する

  • graph[v] の末尾に u を追加する

• color : 色情報を格納する辞書（マップ）を新しく用意する

• 関数 dfs() を定義する。引数は u、c（初期値は0）

• u が color に既に存在する場合

  • color[u] が c と一致していれば true を返す

• color[u] := c とし、graph[u] 内の各 v に対して dfs(v, c XOR 1) を呼び出し、その結果がすべて true なら true を返す

• メイン処理では次を行う

• 0 から n までの各 u について（u が color に存在しない場合のみ）dfs(u) を実行し、すべて true なら true を返す

実装例

理解を深めるために、次のコードを見てみましょう。

class Solution:
    def solve(self, n, enemies):
        from collections import defaultdict
        graph = defaultdict(list)
        for u, v in enemies:
            graph[u].append(v)
            graph[v].append(u)
        color = {}
        def dfs(u, c=0):
            if u in color:
                return color[u] == c
            color[u] = c
            return all(dfs(v, c ^ 1) for v in graph[u])
        return all(dfs(u) for u in range(n) if u not in color)
ob = Solution()
n = 4
enemies = [[0, 3],[3, 2]]
print(ob.solve(n, enemies))

入力

4, [[0, 3],[3, 2]]

出力

True

このアルゴリズムでは、各頂点（人）を訪問するたびに反対の色（c XOR 1）を隣接ノードに割り当てていくため、矛盾なく塗り分けられれば2グループへの分割が可能であることがわかります。計算量は頂点数と辺数に比例する O(N + E) となり、効率的な解法です。