C++ প্রোগ্রাম: গ্রাফে শর্ত অনুযায়ী সর্বোচ্চ বিভাগ সংখ্যা গণনা

মান লিখুন: আমাদের কাছে একটি গ্রাফ G-এর এডজেসেন্সি ম্যাট্রিক্স রয়েছে। যাচাই করতে হবে যে কি ভার্টেক্সগুলোকে নন-এম্পটি সেট V1, V2, ..., Vk-তে ভাগ করা যায় যাতে: প্রতিটি এজ দুটি সन्नিহিত সেটের ভার্টেক্সকে সংযুক্ত করে। যদি হয়, তবে সর্বোচ্চ সম্ভাব্য k এর মান বের করতে হবে।

উদাহরণ

ইনপুট ম্যাট্রিক্স (চিত্রে দেখানো হয়েছে) দিয়ে আউটপুট হবে 4।

সমাধানের ধাপসমূহ

dp অ্যারে (আকার ২১০)
n := ম্যাট্রিক্সের আকার
fl := 1, ans := 0
for i := 0 থেকে n-1 এবং fl:
    dp -1 দিয়ে ফিল করুন
    dp[i] := 0
    q কিউ, i পুশ করুন
    যতক্ষণ q খালি নয়:
        x := q.front(), q.pop()
        for j := 0 থেকে n-1:
            যদি matrix[x][j] == 1:
                যদি dp[j] == -1:
                    dp[j] := dp[x] + 1, q.push(j)
                অন্যথায় যদি |dp[j]-dp[x]| != 1:
                    fl := 0
    for j := 0 থেকে n-1: 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, 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 } }