C++で解く「可能な2分割」問題 ― DFSによる2部グラフ判定の実装

N人の人たち（番号は1、2、…、N）がおり、全員を任意のサイズの2つのグループに分割したいと考えます。ただし、それぞれの人は他の人を嫌っている場合があり、嫌いな相手とは同じグループに入ることができません。すなわち、dislikes[i] = [a, b] は、番号aと番号bの人を同じグループに入れてはならないことを意味します。この条件下で、全員を2つのグループに分割できるかどうかを判定するのが本記事のテーマです。

たとえば、入力がN = 4、dislikes = [[1,2],[1,3],[2,4]] の場合、出力は true となり、グループは [1,4] と [2,3] に分けられます。

この問題は本質的に「2部グラフ（バイパータイトグラフ）の判定」であり、人間関係をグラフの頂点と辺とみなして、隣接する頂点同士が必ず異なる色になるように2色へ塗り分けられるかを確認する問題として捉えることができます。

アルゴリズムの流れ

この問題は、深さ優先探索（DFS）を用いたグラフの塗り分けによって効率的に解くことができます。全体の流れは以下の通りです。

dfs() メソッドの処理

• set型の配列groupsを用意し、2つのグループを表現する

• node（現在のノード）、graph（隣接リスト）、x（グループ番号）を受け取るdfs()メソッドを作成する

• aux := 1 − x（反対側のグループ番号）とする

• groups[aux]にnodeが既に存在する場合はfalseを返す（矛盾）

• nodeをgroups[x]に挿入する

• iを0からgraph[node]のサイズ − 1までループさせる

  • u := graph[node][i]

  • groups[aux]にuが存在せず、かつdfs(u, graph, aux)がfalseを返す場合はfalseを返す

• それ以外の場合はtrueを返す

mainメソッドの処理

• サイズ[N + 1]の隣接リストgraphを作成する

• iを0からdislikesのサイズ − 1までループさせる

  • u := dislikes[i][0]、v := dislikes[i][1]

  • graph[u]にvを追加し、graph[v]にuを追加する（無向グラフとして構築）

• iを1からNまでループさせる

  • groups[0]にもgroups[1]にもiが含まれていない未訪問ノードの場合

    • dfs(i, graph, 0)がfalseを返すなら、全体としてfalseを返す

• すべてのノードを矛盾なく割り振れたらtrueを返す

C++による実装例

理解を深めるため、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    set<int> groups[2];
    bool dfs(int node, vector<int> graph[], int x){
        int aux = 1 - x;
        if(groups[aux].count(node)) return false;
        groups[x].insert(node);
        for(int i = 0; i < graph[node].size(); i++){
            int u = graph[node][i];
            if(!groups[aux].count(u) && !dfs(u, graph, aux)) return false;
        }
        return true;
    }
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<int> graph[N + 1];
        for(int i = 0; i < dislikes.size(); i++){
            int u = dislikes[i][0];
            int v = dislikes[i][1];
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        for(int i = 1; i <= N; i++){
            if(!groups[0].count(i) && !groups[1].count(i)){
                if(!dfs(i, graph, 0)) return false;
            }
        }
        return true;
    }
};
int main(){
    vector<vector<int>> v = {{1,2},{1,3},{2,4}};
    Solution ob;
    cout << (ob.possibleBipartition(4, v));
    return 0;
}

入力

4
[[1,2],[1,3],[2,4]]

出力

true

コードのポイント

まず、dislikesリストから隣接リスト形式の無向グラフを構築します。次に、まだどちらのグループにも割り当てられていないノードを起点としてDFSを開始します。dfs関数では、現在のノードをグループxに配置したうえで、隣接ノードをすべて反対側のグループauxへ再帰的に割り当てていきます。

探索の過程で、隣接ノードがすでに自分と同じグループxに属している場合は矛盾となるためfalseが返されます。一方、すでに反対グループauxに属しているノードは再探索をスキップすることで、無駄な計算を避けています。連結していないグラフにも対応できるよう、main側では全ノードを走査し、未割り当てのノードごとに新たにDFSを起動している点も重要です。

計算量については、各ノードと各辺が高々一度ずつ処理されるため、概ね O(N + E)（Eはdislikesのペア数）で抑えられます。なお、setを使用しているため、各挿入・検索操作には対数時間のコストが伴います。より高速化が必要な場合は、配列ベースのカラーリング（各頂点に0/1/-1の状態を持たせる方式）に置き換えることも有効です。