গাছের ব্যাস C++ এ

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

আউটপুট হবে 4.

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি মানচিত্র সংজ্ঞায়িত করুন l
• dfs() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন। এটি ভিজিটেড নামক একটি অ্যারে, গ্রাফ এবং গ নেবে। এটি নিম্নরূপ কাজ করবে -
• ভিজিট করা হয়েছে[v] :=true, সেট উত্তর :=0
• আমি 0 থেকে গ্রাফের আকার [v]
  পরিসরে
  • যদি পরিদর্শন করা হয় [গ্রাফ[v, i]] মিথ্যা হয়, তাহলে
    • উত্তর :=উত্তরের সর্বোচ্চ, dfs(গ্রাফ[v, i], পরিদর্শন করা, গ্রাফ, c + 1)
• যদি c> সেরা, তাহলে সেরা :=c এবং নোড :=v
• সেট পরিদর্শন করা হয়েছে[v] :=মিথ্যা
• গ এবং উত্তরের সর্বোচ্চ রিটার্ন
• প্রধান পদ্ধতিতে, এটি এজ লিস্ট ই নেবে
• n :=e এর আকার, n + 1 আকারের গ্রাফ নামে একটি অ্যারে তৈরি করুন
• আমি 0 থেকে n – 1
  পরিসরে
  • গ্রাফ[e[i, 0]]-এ e[i, 1] ঢোকান এবং গ্রাফে [e[i, 1]]] ঢোকান
• n + 1 আকারের দুটি অ্যারে পরিদর্শন করুন এবং পরিদর্শন করা 2 অ্যারে করুন, সেরা সেট করুন :=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]]

আউটপুট

4