C++-এ গাছের দূরত্বের যোগফল

ধরুন আমাদের একটি অনির্দেশিত, সংযুক্ত গাছ আছে যেখানে N নোড উপস্থিত রয়েছে। এই 0 হিসাবে লেবেল করা হয়...N-1 এবং N-1 প্রান্ত দেওয়া হয়. ith প্রান্তটি নোডের প্রান্ত [i][0] এবং প্রান্তগুলিকে [i][1] একসাথে সংযুক্ত করে। আমাদের একটি তালিকা খুঁজে বের করতে হবে যেখানে ans[i] হল নোড i এবং অন্যান্য সমস্ত নোডের মধ্যে দূরত্বের সমষ্টি৷

সুতরাং, যদি ইনপুট হয় N =6 এবং প্রান্ত =[(0,1),(0,2),(2,3),(2,4),(2,5)], তাহলে আউটপুট হবে [8,12,6,10,10,10]

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

• একটি ফাংশন dfs1() সংজ্ঞায়িত করুন, এটি নোড, প্যারেন্ট,

  নেবে

  • আরম্ভ করার জন্য i :=0, যখন i <গ্রাফের আকার [নোড], আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), করুন −

    • শিশু :=গ্রাফ[নোড, i]

    • যদি সন্তান পিতামাতার সমান না হয়, তাহলে -

      • dfs1(শিশু, নোড)

      • cnt[নোড] :=cnt[নোড] + cnt[শিশু]

      • ans[নোড] :=ans[নোড] + cnt[child] + ans[child]

• একটি ফাংশন dfs2() সংজ্ঞায়িত করুন, এটি নোড, প্যারেন্ট,

  নেবে

  • আরম্ভ করার জন্য i :=0, যখন i <গ্রাফের আকার [নোড], আপডেট (i 1 দ্বারা বৃদ্ধি), do−

    • শিশু :=গ্রাফ[নোড, i]

    • যদি সন্তান পিতামাতার সমান না হয়, তাহলে -

      • ans[শিশু] :=ans[নোড] - cnt[child] + N - cnt[child]

      • dfs2(শিশু, নোড

• একটি অ্যারে উত্তর সংজ্ঞায়িত করুন

• একটি অ্যারে cnt

  সংজ্ঞায়িত করুন

• 10005 সারি সহ একটি অ্যারে গ্রাফ সংজ্ঞায়িত করুন

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

• এর N :=N

• উত্তর :=N

  আকারের একটি অ্যারের সংজ্ঞা দাও

• cnt :=N আকারের একটি অ্যারে নির্ধারণ করুন, এটি 1 দিয়ে পূরণ করুন

• n :=প্রান্তের আকার

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

  • u :=প্রান্ত[i, 0]

  • v :=প্রান্ত[i, 1]

  • গ্রাফ[u]

    -এর শেষে v সন্নিবেশ করান

  • গ্রাফের শেষে u ঢোকান[v]

• dfs1(0, -1)

• dfs2(0, -1)

• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0;
   i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   void dfs1(int node, int parent) {
      for (int i = 0; i < graph[node].size(); i++) {
         int child = graph[node][i];
         if (child != parent) {
            dfs1(child, node);
            cnt[node] += cnt[child];
            ans[node] += cnt[child] + ans[child];
         }
      }    
   }
   void dfs2(int node, int parent) {
      for (int i = 0; i < graph[node].size(); i++) {
         int child = graph[node][i];
         if (child != parent) {
            ans[child] = ans[node] - cnt[child] + N - cnt[child];
            dfs2(child, node);
         }
      }
   }
   vector<int> ans;
   vector<int> cnt;
   vector<int> graph[10005];
   int N;
   vector<int> sumOfDistancesInTree(int N, vector<vector<int> >& edges) {
      this->N = N;
      ans = vector<int>(N);
      cnt = vector<int>(N, 1);
      int n = edges.size();
      for (int i = 0; i < n; i++) {
         int u = edges[i][0];
         int v = edges[i][1];
         graph[u].push_back(v);
         graph[v].push_back(u);
      }
      dfs1(0, -1);
      dfs2(0, -1);
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1},{0,2},{2,3},{2,4},{2,5}}; print_vector(ob.sumOfDistancesInTree(6,    v));
}

ইনপুট

{{0,1},{0,2},{2,3},{2,4},{2,5}}

আউটপুট

[8, 12, 6, 10, 10, 10, ]