C++ में पेड़ का व्यास

मान लीजिए कि हमारे पास एक अप्रत्यक्ष पेड़ है; हमें इसका व्यास ज्ञात करना है - उस पेड़ के सबसे लंबे पथ में किनारों की संख्या उस पेड़ का व्यास है। यहां पेड़ को किनारे की सूची के रूप में दिया गया है जहां किनारों [i] =[यू, वी] नोड्स यू और वी के बीच एक द्विदिश किनारा है। प्रत्येक नोड में सेट {0, 1, ..., किनारों। लंबाई} में लेबल होते हैं। तो अगर ग्राफ इस तरह है -

आउटपुट 4 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

मानचित्र को परिभाषित करें l
डीएफएस () नामक एक विधि को परिभाषित करें। यह वी ले जाएगा, एक सरणी जिसे विज़िट किया गया, ग्राफ़ और सी कहा जाता है। यह इस प्रकार काम करेगा -
विज़िट किया[v] :=true, set ans :=0
मैं के लिए 0 से ग्राफ़ के आकार की सीमा में[v]
- अगर विज़िट किया गया[ग्राफ[v, i]] गलत है, तो
  - उत्तर :=अधिकतम उत्तर, dfs(ग्राफ[v, i], देखे गए, ग्राफ़, c + 1)
अगर c> सबसे अच्छा है, तो सबसे अच्छा:=c और नोड:=v
विजिट किया गया सेट[v] :=false
सी और उत्तर की अधिकतम वापसी
मुख्य विधि में, यह बढ़त सूची e
n :=e का आकार, आकार n + 1 का ग्राफ़ नामक एक सरणी बनाएं
मैं के लिए 0 से n - 1 की सीमा में
- ई[i, 1] को ग्राफ़ में डालें[e[i, 0]] और e[i, 0] को ग्राफ़ में डालें[e[i, 1]]
दो सरणियों का दौरा करें, और विज़िट की गई2 सरणी आकार n + 1, सर्वोत्तम सेट करें:=0 और नोड:=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]]