C++プログラム：グラフの頂点を条件を満たして分割できる場合の最大分割数を求める

グラフGの隣接行列が与えられたとします。このとき、すべての辺が「隣接する2つの集合」に属する頂点同士を結ぶという条件を満たすように、頂点を空でない集合 V₁, …, V_k に分割できるかどうかを判定します。分割が可能な場合は、そのような分割における集合数 k の最大値を求めてください。

例えば、入力が以下のような隣接行列だったとします。

この場合、出力は 4 となります。

アプローチの考え方

この問題は、各頂点をBFS（幅優先探索）による始点からの距離（レベル）で分類することで解けます。条件を満たす分割では、すべての辺がレベル差ちょうど1の頂点同士を結んでいなければなりません。もしレベル差が1以外の辺が存在すれば、そのような分割は不可能であると判断できます。各頂点を始点としてBFSを行い、整合性を確認しながら最大レベルを求めるのが基本的な方針です。

解法の手順

この問題を解くために、以下の手順に従います。

サイズ210の配列dpを定義する。
n := 行列のサイズ
fl := 1（整合性フラグ）
ans := 0
i := 0 から i < n かつ fl が0でない間、i を1ずつ増やしながら繰り返す：
　　dp を -1 で初期化する
　　dp[i] := 0
　　キューqを用意し、i を挿入する
　　q が空でない間、繰り返す：
　　　　x := q の先頭要素を取り出す
　　　　j := 0 から j < n の間、j を1ずつ増やしながら繰り返す：
　　　　　　matrix[x][j] が 1 の場合：
　　　　　　　　dp[j] が -1 の場合：
　　　　　　　　　　dp[j] := dp[x] + 1
　　　　　　　　　　j を q に挿入する
　　　　　　　　そうでなく |dp[j] - dp[x]| が 1 と等しくない場合：
　　　　　　　　　　fl := 0
　　j := 0 から j < n の間、ans := max(ans, dp[j]) を更新する
fl が 0 の場合：
　　-1 を返す
それ以外の場合：
　　ans + 1 を返す

実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> matrix){
   int dp[210];
   int n = matrix.size();
   int fl = 1;
   int ans = 0;
   for (int i = 0; i < n && fl; i++){
      memset(dp, -1, sizeof(dp));
      dp[i] = 0;
      queue<int> q;
      q.push(i);
      while (!q.empty()){
         int x = q.front();
         q.pop();
         for (int j = 0; j < n; j++){
            if (matrix[x][j] == 1){
               if (dp[j] == -1){
                  dp[j] = dp[x] + 1;
                  q.push(j);
               }
               else if (abs(dp[j] - dp[x]) != 1)
                  fl = 0;
            }
         }
      }
      for (int j = 0; j < n; j++)
         ans = max(ans, dp[j]);
   }
   if (fl == 0){
      return -1;
   }else{
      return ans + 1;
   }
}
int main(){
   vector<vector<int>> matrix = { { 0, 1, 0, 1, 1, 0 }, { 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0 } };
   cout << solve(matrix) << endl;
}

入力

{ { 0, 1, 0, 1, 1, 0 }, { 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0 } }

出力

4

計算量について

このアルゴリズムは、各頂点を始点としてBFSを実行するため、時間計算量は O(n³) となります（nは頂点数）。頂点数が数百程度までのグラフであれば十分に高速に動作します。また、どの始点から見ても辺の両端のレベル差が必ず1になることが確認できれば、そのグラフは条件を満たす分割が可能であり、答えは最大レベル + 1（= 集合の個数）になります。