Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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

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

उदाहरण के लिए, यदि N = 6 और edges = [(0,1),(0,2),(2,3),(2,4),(2,5)], तो आउटपुट [8,12,6,10,10,10] होगा।

हल करने का दृष्टिकोण

हम दो-पास DFS का उपयोग करते हैं:

  • पहला DFS (पोस्ट-ऑर्डर): प्रत्येक नोड के लिए सबट्री आकार (cnt) और सबट्री के भीतर दूरियों का योग (ans) की गणना करें

  • दूसरा DFS (प्री-ऑर्डर): पैरेंट के उत्तर का उपयोग करके प्रत्येक बच्चे के लिए उत्तर की गणना करें: ans[child] = ans[parent] - cnt[child] + N - cnt[child]

  • यह O(N) में सभी नोड्स के लिए उत्तर देता है

उदाहरण

#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; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<int>> v = {{0,1},{0,2},{2,3},{2,4},{2,5}}; 
    print_vector(ob.sumOfDistancesInTree(6, v)); 
    return 0;
}

इनपुट

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

आउटपुट

[8, 12, 6, 10, 10, 10, ]
  1. C++ में ट्री नोड्स डिलीट करें C++ में ट्री नोड्स डिलीट करें

    मान लीजिए हमारे पास एक ट्री है, यह ट्री नोड 0 पर रूटेड है, यह निम्नानुसार दिया गया है -नोड्स की संख्या nodes हैi-वें नोड का मान value[i] हैi-वें नोड का पैरेंट parent[i] हैहमें हर उस सबट्री को हटाना है जिसके नोड्स के मानों का योग 0 है, ऐसा करने के बाद ट्री में शेष नोड्स की संख्या लौटाएं। यदि ट्री इस

  1. C++ में ट्री डायमीटर C++ में ट्री डायमीटर

    मान लीजिए हमारे पास एक अनडायरेक्टेड ट्री है; हमें इसका डायमीटर ढूंढना है - उस ट्री में सबसे लंबे पथ में एज की संख्या उस ट्री का डायमीटर है। यहां ट्री को एज लिस्ट के रूप में दिया गया है जहां edges[i] = [u, v] नोड्स u और v के बीच एक बायडायरेक्शनल एज है। प्रत्येक नोड के लेबल सेट {0, 1, ..., edges.lengt

  1. बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में

    मान लीजिए हमारे पास एक बाइनरी ट्री है। कार्य वर्टिकल ऑर्डर ट्रैवर्सल में सभी नोड्स के योग के अधिकतम को प्रिंट करना है। तो यदि ट्री नीचे जैसा है - वर्टिकल ऑर्डर ट्रैवर्सल इस तरह है - 4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9 यहां अधिकतम 12 है। दृष्टिकोण सरल है। हम वर्टिकल ऑर्डर ट्रैवर्सल करेंगे, फिर योग खोज