C++에서 트리의 거리 합계

N개의 노드가 있는 하나의 무방향, 연결된 트리가 있다고 가정합니다. 이들은 0...N-1으로 레이블이 지정되고 N-1 모서리가 제공됩니다. i번째 에지는 노드 edge[i][0]와 edge[i][1]를 함께 연결합니다. ans[i]가 노드 i와 다른 모든 노드 사이의 거리의 합인 목록을 찾아야 합니다.

따라서 입력이 N =6이고 edge =[(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[자식] + ans[자식]

• dfs2() 함수를 정의하면 노드, 부모,

  가 사용됩니다.

  • for initialize i :=0, i

    • 자식 :=그래프[노드, i]

    • 자식이 부모와 같지 않으면 -

      • ans[자식] :=ans[노드] - cnt[자식] + N - cnt[자식]

      • dfs2(자식, 노드

• 배열 정의

• 배열 cnt 정의

• 10005개의 행이 있는 배열 그래프 정의

• 기본 방법에서 다음을 수행하십시오 -

• 이 중 N :=N

• ans :=크기가 N인 배열 정의

• cnt :=크기가 N인 배열을 정의하고 1로 채웁니다.

• n :=가장자리 크기

• initialize i :=0의 경우, i

  • u :=가장자리[i, 0]

  • v :=가장자리[i, 1]

  • 그래프 끝에 v 삽입[u]

  • 그래프 끝에 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, ]