C++ এ একটি গাছে সমস্ত আপেল সংগ্রহ করার ন্যূনতম সময়

ধরুন আমাদের n শীর্ষবিন্দু নিয়ে গঠিত একটি অনির্দেশিত গাছ আছে এবং এগুলোকে 0 থেকে n-1 পর্যন্ত সংখ্যা করা হয়েছে, যেটির শীর্ষবিন্দুতে কিছু আপেল রয়েছে। আমরা গাছের এক প্রান্ত ধরে হাঁটতে 1 সেকেন্ড ব্যয় করি। গাছের সমস্ত আপেল সংগ্রহ করার জন্য আমাদের সেকেন্ডের মধ্যে ন্যূনতম সময় খুঁজে বের করতে হবে 0 থেকে শুরু করে এবং এই শীর্ষে ফিরে আসতে।

এখানে অনির্দেশিত গাছের প্রান্তগুলি অ্যারে প্রান্তে দেওয়া হয়েছে, যেখানে প্রান্তগুলি [i] =[from_i, to_i] এর মানে হল যে একটি প্রান্ত রয়েছে যা from_i এবং to_i শীর্ষবিন্দুগুলিকে সংযুক্ত করে। উপরন্তু, আরেকটি অ্যারে আছে আপেল আছে, যেখানে hasApple[i] =সত্য মানে ভার্টেক্স i একটি আপেল আছে, অন্যথায়, এটিতে কোনো আপেল নেই।

সুতরাং, যদি ইনপুট হয় n =7 এবং প্রান্ত =[[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]] , এবং আপেল =[মিথ্যা, মিথ্যা, সত্য, মিথ্যা, সত্য, সত্য, মিথ্যা], তাহলে আউটপুট হবে 8,

উপরের চিত্র থেকে আমরা গাছটি দেখতে পাচ্ছি যেখানে লাল শীর্ষে একটি আপেল রয়েছে। সমস্ত আপেল সংগ্রহের একটি সর্বোত্তম পথ সবুজ তীর দ্বারা দেখানো হয়েছে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• পরিদর্শন করা একটি সেট সংজ্ঞায়িত করুন

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি নোড, par, একটি অ্যারে a, একটি অ্যারে গ্রাফ[],

  নেবে

• তাপমাত্রা :=0

• গ্রাফ[নোড] -

  -এ প্রতিটি উপাদান x এর জন্য

  • যদি x সমান হয়, তাহলে −

    • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

  • temp :=temp + dfs(x, node, a, graph)

• ret :=ret + temp * 2

• সত্য প্রত্যাবর্তন করুন যখন a[node] + temp> 0, অন্যথায় 0

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• ret :=0

• গ্রাফ

  নামে n তালিকার একটি বিন্যাস সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • গ্রাফ[e[i, 0]]

    এর শেষে e[i, 1] ঢোকান

  • গ্রাফ[e[i, 1]]

    এর শেষে e[i, 0] ঢোকান

• 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}

আউটপুট

8