एक फॉरेस्ट (ट्री का संग्रह) के वर्टेक्स दिए गए हैं। लक्ष्य उस फॉरेस्ट में ट्री की संख्या ढूंढना है। हम इसे फॉरेस्ट पर DFS (डेप्थ फर्स्ट सर्च) एल्गोरिदम चलाकर करेंगे।
उदाहरण के लिए
इनपुट
edges = { { 1,3 }, {2,8}, {2,6}, {3,5}, {3,7}, {4,8} } आउटपुट
Count of number of trees in a forest are: 3
व्याख्या
फॉरेस्ट में मौजूद ट्री की संख्या हैं:
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:
इस दृष्टिकोण में हम ग्राफ पर रिकर्सिवली डेप्थ फर्स्ट सर्च एल्गोरिदम लागू करते हैं। यदि एक स्रोत से हर कनेक्टेड नोड को विजिटेड मार्क किया जाता है (जिसका मतलब है एक ट्री बन गया है) तो हम गिनती बढ़ाएंगे।
एक पूर्णांक vertice लें जो ग्राफ पर वर्टेक्स की संख्या है।
वेक्टर vector
vec[vertice] लें वर्टेक्स को पूर्णांक के रूप में स्टोर करने के लिए। फ़ंक्शन insert(vector
vec[], int parent, int child) vec[] लेता है और उस वेक्टर में पैरेंट और चाइल्ड नोड्स के बीच एक एज जोड़ता है। vec[parent].push_back(child) और vec[child].push_back(parent) का उपयोग करके एज जोड़ें।
फ़ंक्शन recurred(int temp, vector
vec[], vector &check) शुरुआती वर्टेक्स temp से ग्राफ पर DFS लागू करता है। सरणी check[temp] का उपयोग नोड्स को विजिटेड/अनविजिटेड के रूप में मार्क करने के लिए true/false का उपयोग करके किया जाता है।
फॉर लूप का उपयोग करके वेक्टर vec[] को ट्रैवर्स करें और यदि check[vec[temp][i]] फॉल्स है तो कनेक्टेड नोड्स के लिए recurred(vec[temp][i], vec, check) को रिकर्सिवली कॉल करें।
फ़ंक्शन Trees_Forest(vector
vec[], int vertice) vec[] लेता है और vec[] में एडजेसेंसी लिस्ट के रूप में दिए गए फॉरेस्ट में ट्री की संख्या लौटाता है। फॉरेस्ट की प्रारंभिक गिनती को 0 के रूप में लें।
वेक्टर
check(vertice, false) लें ग्राफ के वर्टेक्स को विजिटेड के रूप में मार्क करने के लिए। फॉर लूप का उपयोग करके सभी वर्टेक्स को ट्रैवर्स करें।
यदि check[i] फॉल्स है तो recurred(i, vec, check) का उपयोग करके DFS लागू करें और गिनती बढ़ाएं।
सभी लूप के अंत में परिणाम के रूप में गिनती लौटाएं।
उदाहरण
#include<bits/stdc++.h> using namespace std; void insert(vectorvec[], int parent, int child){ vec[parent].push_back(child); vec[child].push_back(parent); } void recurred(int temp, vector vec[], vector &check){ check[temp] = true; int size = vec[temp].size(); for(int i = 0; i < size; i++){ if (check[vec[temp][i]] == false){ recurred(vec[temp][i], vec, check); } } } int Trees_Forest(vector vec[], int vertice){ int count = 0; vector check(vertice, false); for(int i = 0; i < vertice; i++){ if(check[i] == false){ recurred(i, vec, check); count++; } } return count; } int main(){ int vertice = 9; vector vec[vertice]; insert(vec, 1, 3); insert(vec, 2, 8); insert(vec, 2, 6); insert(vec, 3, 5); insert(vec, 3, 7); insert(vec, 4, 8); cout<<"Count of number of trees in a forest are: "<<Trees_Forest(vec, vertice); return 0; }
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:
Count of number of trees in a forest are: 3
