সর্বাধিক সম্ভাব্য বিভাজন গণনা করার জন্য 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