हमें नोड्स और एज वाला एक ग्राफ दिया गया है। लक्ष्य उन नोड्स की अधिकतम संभव संख्या ढूंढना है जो ग्राफ की किसी भी एज से जुड़े नहीं हैं। हम जानते हैं कि नोड्स की संख्या हमेशा एक पूर्ण ग्राफ में एज की संख्या से कम या बराबर होगी।
हम इसे एक पूर्ण ग्राफ बनाने की कोशिश करके करेंगे जहां नोड्स की संख्या n है तो एज की संख्या n(n-1)/2 होगी।
edge = n(n-1)/2 (यहां n नोड्स के लिए)
2*edge = n(n-1)। एक बार n(n-1) > एज की संख्या होने पर हमारे पास अतिरिक्त नोड्स होंगे। इसलिए i=1 से i=n तक पुनरावृति करते हैं।
जब तक i(i-1) > 2*edge। n-i को परिणाम के रूप में लौटाते हैं।
आइए उदाहरणों से समझते हैं -
इनपुट - nodes=5, edges=2
आउटपुट - ग्राफ में किसी भी एज का हिस्सा नहीं होने वाले नोड्स की अधिकतम संख्या: 2
व्याख्या -
2 एज में न्यूनतम 3 नोड्स और अधिकतम 4 नोड्स हो सकते हैं।
3 नोड्स के लिए बिना किसी एज के बचे नोड्स की अधिकतम संख्या = 2
इनपुट - nodes=2, edges=1
आउटपुट - ग्राफ में किसी भी एज का हिस्सा नहीं होने वाले नोड्स की अधिकतम संख्या: 0
व्याख्या -
कम से कम 2 नोड्स एक एज बनाने के लिए आवश्यक हैं। इस मामले में दोनों व्यस्त हैं। कोई नोड नहीं बचा।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
हम उपलब्ध डेटा के लिए दो वेरिएबल nodes और edges लेते हैं।
फंक्शन maximum(int nodes, int edges) नोड्स और एज की संख्या को पैरामीटर के रूप में लेता है और ग्राफ में किसी भी एज का हिस्सा नहीं होने वाले अधिकतम नोड्स की गिनती लौटाता है।
वेरिएबल i, temp और max लेते हैं।
FOR लूप i=0 से i<=nodes तक शुरू करते हैं।
temp = i*(i-1) की गणना करते हैं।
वेरिएबल total की गणना 2*edges के रूप में करते हैं।
जब भी temp, total से अधिक हो जाता है, FOR लूप को तोड़ते हैं।
max की गणना nodes-i के रूप में करते हैं।
परिणाम को max के रूप में लौटाते हैं।
उदाहरण
#include <bits/stdc++.h> using namespace std; int maximum(int nodes, int edges){ int i, temp = 0, max; for (i = 0; i <= nodes; i++){ temp = i * (i - 1); int total = 2* edges; if (temp >= total){ break; } } max = nodes - i; return max; } int main(){ int nodes = 10; int edges = 5; cout<<"ग्राफ में किसी भी एज का हिस्सा नहीं होने वाले नोड्स की अधिकतम संख्या: "<<maximum(nodes, edges) << endl; } आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा -
ग्राफ में किसी भी एज का हिस्सा नहीं होने वाले नोड्स की अधिकतम संख्या: 6
