주어진 조건에서 그래프에서 가능한 최대 나눗셈을 계산하는 C++ 프로그램을 만들 수 있습니다.

그래프 G의 인접 행렬이 있다고 가정합니다. 정점을 비어 있지 않은 집합 V1, ... Vk로 나눌 수 있는지 확인해야 합니다. 모든 모서리는 두 개의 인접한 집합에 속하는 두 정점을 연결합니다. 대답이 예라면 그러한 나눗셈에서 집합 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