C++-এ ট্রি ডায়ামিটার

মনে করুন একটি আনডিরেক্টেড ট্রি আছে; আমাদের এর ডায়ামিটার বের করতে হবে - সেই ট্রির সবচেয়ে লম্বা পথের এজ সংখ্যাই সেটি ডায়ামিটার। এখানে ট্রি এজ লিস্ট হিসেবে দেওয়া আছে যেখানে `edges[i] = [u, v]` হলো নোড `u` এবং `v`-এর মধ্যকার বাইডিরেকশনাল এজ। প্রতিটি নোডের লেবেল সেট `{0, 1, ..., edges.length}`-এ থাকে। যদি গ্রাফ নিচের মোতাবিক হয় -

আউটপুট হবে ৪।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -

একটি ম্যাপ `l` সংজ্ঞায়িত করুন
`dfs()` নামক একটি মেথড সংজ্ঞায়িত করুন। এটি `v`, `visited` অ্যারে, `graph` এবং `c` নেবে। এটি নিচের মোতাবিক কাজ করবে -
`visited[v] := true`, `ans := 0` সেট করুন
`i` = 0 থেকে `graph[v]`-এর আকার পর্যন্ত
- যদি `visited[graph[v][i]]` false হয়, তবে
  - `ans := max(ans, dfs(graph[v][i], visited, graph, c + 1))`
যদি `c > best`, তবে `best := c` এবং `node := v`
`visited[v] := false` সেট করুন
`max(c, ans)` রিটার্ন করুন
মেইন মেথডে, এটি এজ লিস্ট `e` নেবে
`n := e`-এর আকার, `graph` নামক একটি অ্যারে আকার `n + 1` তৈরি করুন
`i` = 0 থেকে `n-1` পর্যন্ত
- `e[i][1]`-কে `graph[e[i][0]]`-এ এবং `e[i][0]`-কে `graph[e[i][1]]`-এ ইনসার্ট করুন
`visited` এবং `visited2` নামক দুটি অ্যারে আকার `n + 1` তৈরি করুন, `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]]