เส้นผ่านศูนย์กลางของต้นไม้ใน C++

สมมุติว่าเรามีต้นไม้ที่ไม่มีทิศทาง เราต้องหาเส้นผ่านศูนย์กลางของมัน - จำนวนขอบในเส้นทางที่ยาวที่สุดในต้นไม้นั้นคือเส้นผ่านศูนย์กลางของต้นไม้นั้น ต้นไม้ที่นี่ถูกกำหนดเป็นรายการขอบโดยที่ edge[i] =[u, v] เป็นขอบแบบสองทิศทางระหว่างโหนด u และ v แต่ละโหนดมีป้ายกำกับในชุด {0, 1, ..., edge.length} ดังนั้นหากกราฟเป็นเช่น −

ผลลัพธ์จะเป็น 4.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดแผนที่ l
• กำหนดวิธีการที่เรียกว่า dfs() นี้จะใช้เวลา v, อาร์เรย์ที่เรียกว่าเยี่ยมชม, กราฟและ c มันจะทำงานดังนี้ −
• เยี่ยมชม[v] :=true, set ans :=0
• สำหรับ i ในช่วง 0 ถึงขนาดของกราฟ[v]
  • ถ้าเข้าชม[กราฟ[v, i]] จะเป็นเท็จ ดังนั้น
    • ans :=สูงสุดของ ans, dfs(graph[v, i], visit, graph, c + 1)
• ถ้า c> ดีที่สุด ก็ดีที่สุด :=c และ node :=v
• ตั้งค่าการเยี่ยมชม[v] :=false
• คืนค่าสูงสุดของ c และ ans
• ในวิธีหลัก จะเอา edge list e
• n :=ขนาดของ e สร้างอาร์เรย์ที่เรียกว่ากราฟขนาด n + 1
• สำหรับ i ในช่วง 0 ถึง n – 1
  • แทรก e[i, 1] ลงในกราฟ[e[i, 0]] และแทรก e[i, 0] ลงในกราฟ[e[i, 1]]
• สร้างอาร์เรย์สองอาร์เรย์ที่เข้าชมและเยี่ยมชม2 อาร์เรย์ขนาด n + 1 ให้ดีที่สุด :=0 และโหนด :=0
• โทร dfs(0, เยี่ยมชม, กราฟ)
• ส่งคืน dfs(โหนด, visit2, กราฟ)

ตัวอย่าง(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]]

ผลลัพธ์

4