Tổng khoảng cách trong cây trong C ++

Giả sử chúng ta có một cây vô hướng, được kết nối với N nút hiện diện. Chúng được gắn nhãn là 0 ... N-1 và N-1 cạnh được cho trước. Cạnh thứ i nối các cạnh nút [i] [0] và cạnh [i] [1] với nhau. Chúng ta phải tìm một danh sách trong đó ans [i] là tổng khoảng cách giữa nút i và tất cả các nút khác.

Vì vậy, nếu đầu vào là N =6 và các cạnh =[(0,1), (0,2), (2,3), (2,4), (2,5)], thì đầu ra sẽ là [8,12,6,10,10,10]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm dfs1 (), hàm này sẽ lấy nút, cha,

  • để khởi tạo i:=0, khi i

    • con:=graph [node, i]

    • nếu con không bằng cha mẹ thì -

      • dfs1 (con, nút)

      • cnt [node]:=cnt [node] + cnt [child]

      • ans [node]:=ans [node] + cnt [child] + ans [child]

• Xác định một hàm dfs2 (), hàm này sẽ lấy nút, cha,

  • để khởi tạo i:=0, khi i

    • con:=graph [node, i]

    • nếu con không bằng cha mẹ thì -

      • ans [child]:=ans [node] - cnt [child] + N - cnt [child]

      • dfs2 (con, nút

• Xác định ans mảng

• Xác định một mảng cnt

• Xác định một biểu đồ mảng có 10005 hàng

• Từ phương thức chính, thực hiện như sau -

• N trong số này:=N

• ans:=Xác định một mảng có kích thước N

• cnt:=Xác định một mảng có kích thước N, điền vào đây là 1

• n:=kích thước của các cạnh

• để khởi tạo i:=0, khi i

  • u:=edge [i, 0]

  • v:=edge [i, 1]

  • chèn v vào cuối biểu đồ [u]

  • chèn u vào cuối biểu đồ [v]

• dfs1 (0, -1)

• dfs2 (0, -1)

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

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