अवधारणा
एक दिए गए अनडायरेक्टेड ग्राफ के संबंध में, सत्यापित करें कि क्या इसमें आकार 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

उपरोक्त ग्राफ में आकार 4 का एक इंडिपेंडेंट सेट है (शीर्ष 0, 1, 3, 4 एक-दूसरे से सीधे जुड़े नहीं हैं)। इसलिए आउटपुट 'Yes' है।
इनपुट
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

आरेख में, उपरोक्त ग्राफ में आकार 4 का इंडिपेंडेंट सेट नहीं है। इसलिए आउटपुट 'No' है।
विधि
<उल क्लास="सूची"><ली>सबसे पहले, sol नामक एक वेरिएबल को बूलियन False मान के साथ इनिशियलाइज़ करें।ली><ली>दिए गए ग्राफ से आकार L के शीर्षों के सभी संभावित सेट निर्धारित करें।ली><ली>यह देखा गया है कि यदि आकार l का एक इंडिपेंडेंट सेट मिलता है, तो sol का मान True में बदलें और लौटें।ली><ली>अन्यथा अन्य संभावित सेट्स के लिए जांच जारी रखें।ली><ली>अंत में, यदि sol True है, तो 'Yes' प्रिंट करें अन्यथा 'No' प्रिंट करें।ली>उल>उदाहरण
<प्रि क्लास="प्रिटीप्रिंट नोट्रांसलेट">// C++ code to check if a given graph // contains an independent set of size k #include <bits/stdc++.h> using namespace std; // फ़ंक्शन प्रोटोटाइप दिखाता है bool check1(int[][5], vector<int>&, int); // दिए गए आकार l का एक सेट बनाने वाला फ़ंक्शन bool func(int graph1[][5], vector<int>&arr1, int l, int index1, bool sol1[]){ // सत्यापित करें कि चयनित सेट इंडिपेंडेंट है या नहीं। // sol के मान को True में बदलने और लौटने के लिए उपयोग किया जाता है // यदि यह इंडिपेंडेंट है if (l == 0){ if (check1(graph1, arr1, arr1.size())){ sol1[0] = true; return true; } } else{ // अब आकार l का सेट बनाया जा सकता है भले ही हम // वर्तमान इंडेक्स पर शीर्ष को शामिल न करें। if (index1 >= l){ vector<int> newvec(arr1.begin(), arr1.end()); newvec.push_back(index1); return (func(graph1, newvec, l - 1, index1 - 1, sol1) or func(graph1, arr1, l, index1 - 1, sol1)); } // अब आकार l का सेट नहीं बनाया जा सकता यदि हम // वर्तमान इंडेक्स पर शीर्ष को शामिल न करें। else{ arr1.push_back(index1); return func(graph1, arr1, l - 1, index1 - 1, sol1); } } } // दिए गए सेट को सत्यापित करने वाला फ़ंक्शन कि यह // इंडिपेंडेंट है या नहीं // arr --> आकार l का सेट (शामिल शीर्ष का // इंडेक्स रखता है) bool check1(int graph1[][5], vector<int>&arr1, int n1){ // सत्यापित करें कि प्रत्येक शीर्ष सेट में किसी अन्य // शीर्ष से जुड़ा है या नहीं for (int i = 0; i < n1; i++) for (int j = i + 1; j < n1; j++) if (graph1[arr1[i]][arr1[j]] == 1) return false; return true; } // ड्राइवर कोड 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<int> arr1; // खाली सेट bool sol1[] = {false}; int n1 = sizeof(graph1) / sizeof(graph1[0]); func(graph1, arr1, l, n1 - 1, sol1); if (sol1[0]) cout << "Yes" << endl; else cout << "No" << endl; return 0; }आउटपुट
Yes