C++-এ অনির্দেশিত গ্রাফে নির্দিষ্ট আকারের ইন্ডিপেনডেন্ট সেট আছে কিনা যাচাই

কনসেপ্ট

একটি অনির্দেশিত গ্রাফ এবং আকার L দেওয়া আছে। গ্রাফে L আকারের ইন্ডিপেনডেন্ট সেট (পরস্পর সংযুক্ত নয় এমন ভার্টেক্সের সেট) আছে কিনা যাচাই করুন। হলে "Yes", নয়লে "No"।

ইনপুট ১

L=4, graph=[[1,0,1,0,0],[0,1,1,0,0],[1,1,1,1,1],[0,0,1,1,0],[0,0,1,0,1]]

আউটপুট ১

Yes

ভার্টেক্স 0,1,3,4 ইন্ডিপেনডেন্ট সেট (কোনো এজ নেই)।

ইনপুট ২

L=4, graph=[[1,1,1,0,0],[1,1,1,0,0],[1,1,1,1,1],[0,0,1,1,0],[0,0,1,0,1]]

আউটপুট ২

No

পদ্ধতি

• sol = false ইনিশিয়ালাইজ।
• সব সম্ভাব্য L আকারের ভার্টেক্স সেট জেনারেট করুন (ব্যাকট্র্যাকিং/রিকার্সন)।
• প্রতিটি সেটের জন্য চেক করুন যে কোনো দুটি ভার্টেক্সের মধ্যে এজ আছে কিনা।
• ইন্ডিপেনডেন্ট সেট পেলে sol=true করুন। শেষে sol অনুযায়ী আউটপুট।

উদাহরণ (C++ কোড)

// C++ কোড: গ্রাফে ইন্ডিপেনডেন্ট সেট আছে কিনা
#include <bits/stdc++.h>
using namespace std;

bool check1(int graph1[][5], vector& arr1, int n1) {
    for (int i=0; i& arr1, int l, int index1, bool sol1[]) {
    if (l == 0) {
        if (check1(graph1, arr1, arr1.size())) { sol1[0]=true; return true; }
    } else {
        if (index1 >= l) {
            vector newvec(arr1.begin(), arr1.end());
            newvec.push_back(index1);
            return (func(graph1, newvec, l-1, index1-1, sol1) ||
                    func(graph1, arr1, l, index1-1, sol1));
        } else {
            arr1.push_back(index1);
            return func(graph1, arr1, l-1, index1-1, sol1);
        }
    }
    return false;
}

int main() {
    int graph1[][5] = {{1,0,1,0,0},{0,1,1,0,0},{1,1,1,1,1},{0,0,1,1,0},{0,0,1,0,1}};
    int l = 4;
    vector arr1; bool sol1[] = {false};
    int n1 = sizeof(graph1)/sizeof(graph1[0]);
    func(graph1, arr1, l, n1-1, sol1);
    cout << (sol1[0]?"Yes":"No") << endl;
    return 0;
}

আউটপুট

Yes