最大の可能な分割をカウントするC++プログラムは、与えられた条件でグラフで作成できます

グラフGの隣接行列があるとします。頂点を空でない集合V1、... Vkに分割できるかどうかを確認する必要があります。たとえば、すべてのエッジが2つの隣接する集合に属する2つの頂点を接続します。答えが「はい」の場合、そのような分割で集合kの可能な最大値を見つける必要があります。

したがって、入力が次のような場合

その場合、出力は4になります

ステップ

これを解決するには、次の手順に従います-

Define an array dp of size: 210.
n := size of matrix
fl := 1
ans := 0
for initialize i := 0, when i < n and fl is non-zero, update (increase i by 1), do:
   fill dp with -1
   dp[i] := 0
   Define one queue q
   insert i into q
   while (q is not empty), do:
      x := first element of q
      delete element from q
      for initialize j := 0, when j < n, update (increase j by 1), do:
         if matrix[x, j] is same as 1, then:
            if dp[j] is same as -1, then:
               dp[j] := dp[x] + 1
               insert j into q
            otherwise when |dp[j] - dp[x]| is not equal to 1, then:
               fl := 0
      for initialize j := 0, when j < n, update (increase j by 1), do:
         ans := maximum of ans and dp[j]
if fl is same as 0, then:
   return -1
Otherwise
   return ans + 1

例

理解を深めるために、次の実装を見てみましょう-

#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