सी++ में एक पेड़ में सभी सेबों को इकट्ठा करने का न्यूनतम समय

मान लीजिए कि हमारे पास एक अप्रत्यक्ष पेड़ है जिसमें n शीर्ष हैं और इनकी संख्या 0 से n-1 तक है, जिसके शीर्षों में कुछ सेब हैं। हम पेड़ के एक किनारे पर चलने में 1 सेकंड खर्च करते हैं। पेड़ में सभी सेबों को शीर्ष 0 से शुरू करने और इस शीर्ष पर वापस आने के लिए हमें सेकंड में न्यूनतम समय निकालना होगा।

यहां अप्रत्यक्ष पेड़ के किनारों को सरणी किनारों में दिया गया है, जहां किनारों [i] =[from_i, to_i] इसका मतलब है कि किनारे से_i और to_i को जोड़ने वाला किनारा मौजूद है। इसके अतिरिक्त, एक अन्य सरणी में सेब है, जहां हैएप्पल [i] =सत्य का अर्थ है कि शीर्ष पर मेरे पास एक सेब है, अन्यथा, इसमें कोई सेब नहीं है।

इसलिए, यदि इनपुट n =7 और किनारों =[[0,1], [0,2], [1,4], [1,5], [2,3], [2,6]] की तरह है। , और सेब =[गलत, असत्य, सत्य, असत्य, सत्य, सत्य, असत्य] है, तो आउटपुट 8 होगा,

जैसा कि ऊपर की छवि से हम उस पेड़ को देख सकते हैं जहाँ लाल कोने में एक सेब है। हरे तीरों द्वारा सभी सेबों को इकट्ठा करने का एक इष्टतम मार्ग दिखाया गया है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

देखे गए एक सेट को परिभाषित करें
एक फ़ंक्शन dfs() को परिभाषित करें, यह नोड, बराबर, एक सरणी a, एक सरणी ग्राफ़ [],
लेगा
अस्थायी:=0
ग्राफ में प्रत्येक तत्व x के लिए [नोड] -
- यदि x बराबर के समान है, तो -
  - निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
- अस्थायी:=अस्थायी + डीएफएस (एक्स, नोड, ए, ग्राफ)
रिट:=रिट + टेम्प * 2
सही लौटें जब एक [नोड] + अस्थायी> 0, अन्यथा 0
मुख्य विधि से निम्न कार्य करें -
रिट:=0
n सूचियों की एक सरणी परिभाषित करें जिसे ग्राफ़ कहा जाता है
इनिशियलाइज़ i :=0 के लिए, जब i
- ग्राफ़ के अंत में e[i, 1] डालें[e[i, 0]]
- ग्राफ़ के अंत में e[i, 0] डालें[e[i, 1]]
dfs(0, -1, a, ग्राफ़)
वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
class Solution {
public:
   set<int> visited;
   int ret;
   int dfs(int node, int par, vector<bool>& a, vector<int> graph[]){
      int temp = 0;
      for (int x : graph[node]) {
         if (x == par)
            continue;
         temp += dfs(x, node, a, graph);
      }
      ret += temp * 2;
      return a[node] + temp > 0;
   }
   int minTime(int n, vector<vector<int> >& e, vector<bool>& a){
      ret = 0;
      vector<int> graph[n];
      for (int i = 0; i < e.size(); i++) {
         graph[e[i][0]].push_back(e[i][1]);
         graph[e[i][1]].push_back(e[i][0]);
      }
      dfs(0, -1, a, graph);
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}};
   vector<bool> v1 = {false,false,true,false,true,true,false};
   cout << (ob.minTime(7,v, v1));
}

इनपुट

7, {{0,1},{0,2},{1,4},{1,5},{2,3},{2,6}},
{false,false,true,false,true,true,false}