Chương trình C ++ để đếm phép chia lớn nhất có thể có thể được thực hiện trong một đồ thị với điều kiện cho trước

Giả sử chúng ta có một ma trận kề của đồ thị G. Chúng ta phải kiểm tra xem chúng ta có thể chia các đỉnh thành các tập khác rỗng V1, ... Vk, sao cho:mọi cạnh nối hai đỉnh thuộc hai tập kề nhau. Nếu câu trả lời là có, chúng ta phải tìm giá trị lớn nhất có thể có của tập k, trong phép chia như vậy.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 4

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

{ { 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 } }

Đầu ra

4