मान लीजिए हमारे पास एक अनडायरेक्टेड, कनेक्टेड ट्री है जहां 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, ]