C++ में ट्री डायमीटर

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

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

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

l नामक एक मैप परिभाषित करें
dfs() नामक एक मेथड परिभाषित करें। यह v, visited नामक एक ऐरे, ग्राफ और c लेगा। यह निम्नानुसार काम करेगा -
visited[v] := true, ans := 0 सेट करें
i के लिए 0 से graph[v] के आकार तक की रेंज में
- यदि visited[graph[v, i]] false है, तो
  - ans := ans का मैक्स, dfs(graph[v, i], visited, graph, c + 1)
यदि c > best है, तो best := c और node := v
visited[v] := false सेट करें
c और ans का मैक्स लौटाएं
मेन मेथड में, यह एज लिस्ट e लेगा
n := e का आकार, n + 1 आकार का एक ग्राफ ऐरे बनाएं
i के लिए 0 से n - 1 तक की रेंज में
- e[i, 1] को graph[e[i, 0]] में डालें और e[i, 0] को graph[e[i, 1]] में डालें
n + 1 आकार के दो ऐरे visited, और visited2 बनाएं, best := 0 और node := 0 सेट करें
dfs(0, visited, graph) कॉल करें
dfs(node, visited2, graph) लौटाएं

उदाहरण (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]]