C++의 트리 지름

무방향 트리가 있다고 가정합니다. 우리는 그것의 지름을 찾아야 합니다 - 그 트리에서 가장 긴 경로의 에지의 수는 그 트리의 지름입니다. 여기에서 트리는 edge[i] =[u, v]가 노드 u와 v 사이의 양방향 에지인 에지 목록으로 제공됩니다. 각 노드에는 {0, 1, ..., edge.length} 집합에 레이블이 있습니다. 따라서 그래프가 다음과 같으면 -

C++의 트리 지름

출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

지도 정의 l
dfs()라는 메서드를 정의합니다. 여기에는 v, 방문이라는 배열, 그래프 및 c가 필요합니다. 다음과 같이 작동합니다 -
방문[v] :=true, 설정:=0
0에서 그래프 크기까지의 i에 대해[v]
- 방문한[graph[v, i]]가 거짓이면
  - ans :=ans의 최대값, dfs(graph[v, i], 방문, 그래프, c + 1)
c> 최상이면 최상 :=c 및 노드 :=v
방문 설정[v] :=false
c 및 as의 최대값을 반환
메인 메소드에서는 에지 목록 e를 사용합니다.
n :=e의 크기, n + 1 크기의 그래프라는 배열을 만듭니다.
0 ~ n – 1 범위의 i에 대해
- 그래프[e[i, 0]]에 e[i, 1]을 삽입하고 그래프[e[i, 1]]에 e[i, 0]을 삽입
두 개의 배열을 방문하고 n + 1 크기의 배열을 방문하고, best :=0 및 node :=0으로 설정
dfs(0, 방문, 그래프) 호출
dfs(노드, 방문2, 그래프)를 반환

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
class Solution {
public:
   map <int ,int > l;
   int best;
   int node;
   int dfs(int v, bool* visited, vector <int> graph[], int c = 0){
      visited[v] = true;
      int ans = 0;
      for(int i = 0; i < graph[v].size(); i++){
         if(!visited[graph[v][i]])ans = max(ans,dfs(graph[v][i], visited, graph, c+1));
      }
      if(c > best){
         best = c;
         node = v ;
      }
      visited[v] = false;
      return max(c,ans);
   }
   int treeDiameter(vector<vector<int>>& e) {
      int n = e.size();
      vector <int> graph[n+1];
      for(int i = 0; i < n; i++){
         graph[e[i][0]].pb(e[i][1]);
         graph[e[i][1]].pb(e[i][0]);
      }
      bool* visited = new bool[n+1]();
      best = 0;
      node = 0;
      dfs(0, visited, graph);
      bool* visited2 = new bool[n+1]();
      return dfs(node, visited2, graph);
   }
};
main(){
   vector<vector<int>> v = {{0,1},{1,2},{2,3},{1,4},{4,5}};
   Solution ob;
   cout <<ob.treeDiameter(v);
}

입력

[[0,1],[1,2],[2,3],[1,4],[4,5]]