मान लीजिए हमारे पास n वर्टेक्स वाला एक अनडायरेक्टेड ट्री है जो 0 से n-1 तक नंबर किए गए हैं, जिनके वर्टेक्स में कुछ सेब हैं। हम ट्री के एक एज पर चलने में 1 सेकंड खर्च करते हैं। हमें वर्टेक्स 0 से शुरू करके ट्री में सभी सेब इकट्ठा करने और इस वर्टेक्स पर वापस आने में खर्च होने वाले न्यूनतम समय (सेकंड में) ढूंढना है।
यहाँ अनडायरेक्टेड ट्री के एज edges ऐरे में दिए गए हैं, जहां edges[i] = [from_i, to_i] इसका अर्थ है कि वर्टेक्स from_i और to_i को जोड़ने वाला एक एज मौजूद है। इसके अलावा, एक और ऐरे hasApple है, जहां hasApple[i] = true का अर्थ है कि वर्टेक्स i में एक सेब है, अन्यथा, इसमें कोई सेब नहीं है।
इसलिए, यदि इनपुट है n = 7 और edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], और hasApple = [false, false, true, false, true, true, false], तो आउटपुट 8 होगा,
क्योंकि उपरोक्त छवि से हम देख सकते हैं कि लाल वर्टेक्स में सेब हैं। सभी सेब इकट्ठा करने का एक इष्टतम पथ हरे तीरों द्वारा दिखाया गया है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक सेट visited परिभाषित करें
एक फ़ंक्शन dfs() परिभाषित करें, जो node, par, एक ऐरे a, एक ऐरे graph[] लेगा,
temp := 0
graph[node] के प्रत्येक एलिमेंट x के लिए -
यदि x, par के समान है, तो -
बाकी भाग को अनदेखा करें, अगले इटरेशन पर जाएं
temp := temp + dfs(x, node, a, graph)
ret := ret + temp * 2
true लौटाएं जब a[node] + temp > 0, अन्यथा 0
मुख्य विधि से निम्न करें -
ret := 0
n लिस्ट का एक ऐरे graph परिभाषित करें
i := 0 से शुरू करें, जब i < e का आकार, i बढ़ाते हुए, करें -
e[i, 1] को graph[e[i, 0]] के अंत में डालें
e[i, 0] को graph[e[i, 1]] के अंत में डालें
dfs(0, -1, a, graph)
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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}आउटपुट
8
