C++ में ट्री में दूरियों का योग

मान लीजिए कि हमारे पास एक अप्रत्यक्ष, जुड़ा हुआ पेड़ है जहां एन नोड्स मौजूद हैं। इन्हें 0...N-1 और N-1 किनारों के रूप में लेबल किया गया है। इथ एज नोड्स किनारों [i] [0] और किनारों [i] [1] को एक साथ जोड़ता है। हमें एक सूची ढूंढनी होगी जहां ans[i] नोड i और अन्य सभी नोड्स के बीच की दूरी का योग है।

इसलिए, यदि इनपुट एन =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(बच्चा, नोड)

      • सीएनटी [नोड]:=सीएनटी [नोड] + सीएनटी [बच्चा]

      • उत्तर [नोड]:=उत्तर [नोड] + सीएनटी [बच्चा] + उत्तर [बच्चा]

• फ़ंक्शन dfs2() को परिभाषित करें, यह नोड, पैरेंट,

  . लेगा

  • प्रारंभ करने के लिए i :=0, जब i <ग्राफ़ का आकार [नोड], अद्यतन करें (i से 1 बढ़ाएँ), do−

    • बच्चा:=ग्राफ [नोड, i]

    • अगर बच्चा माता-पिता के बराबर नहीं है, तो -

      • उत्तर [बच्चा]:=उत्तर [नोड] - सीएनटी [चाइल्ड] + एन - सीएनटी [चाइल्ड]

      • dfs2(बच्चा, नोड

• एक सरणी को परिभाषित करें ans

• एक सरणी cnt परिभाषित करें

• 10005 पंक्तियों वाला एक सरणी ग्राफ़ परिभाषित करें

• मुख्य विधि से, निम्न कार्य करें -

• इसमें से एन:=एन

• उत्तर:=आकार एन की एक सरणी को परिभाषित करें

• cnt :=आकार N की एक सरणी परिभाषित करें, इसे 1 से भरें

• n :=किनारों का आकार

• इनिशियलाइज़ i :=0 के लिए, जब i

  • आप:=किनारों[i, 0]

  • वी:=किनारों[i, 1]

  • ग्राफ़ के अंत में 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, ]