C++のツリー内の2つの交差しないパスの最大積

この問題では、n個のノードを持つ無向接続ツリーTが与えられます。私たちのタスクは、C++のツリー内の2つの交差しないパスの最大積を見つけるプログラムを作成することです。

問題の説明 −ツリー内の交差しない2つのパスの最大積を見つける。興味のないすべてのパスを見つけてから、それらの長さの積を見つけます。

問題を理解するために例を見てみましょう

入力

グラフ-

出力

8

説明

考慮される交差しないパスはC-A-B およびF-E-D-G-H 。

長さは2と4です。Product=8。

ソリューションアプローチ

この問題の解決策は、DFSを使用してツリーをトラバースすることです。そして、接続エッジを削除した場合に一意になるパスを見つけます。そして、パス上でナイトレートし、その長さを見つけます。次に、パスをペアにして、それらの長さの積を見つけます。 2つは、製品が最大になるように考慮されます。

ソリューションを実装するためのプログラム

例

#include <bits/stdc++.h>
using namespace std;
int TreeTraverse(vector<int> graph[], int& currPathMax, int val1, int val2){
   int max1 = 0, max2 = 0, maxVal = 0;
   for (int i = 0; i < graph[val1].size(); i++) {
      if (graph[val1][i] == val2)
         continue;
         maxVal = max(maxVal, TreeTraverse(graph, currPathMax,
      graph[val1][i], val1));
      if (currPathMax > max1) {
         max2 = max1;
         max1 = currPathMax;
      }
      else
         max2 = max(max2, currPathMax);
   }
   maxVal = max(maxVal, max1 + max2);
   currPathMax = max1 + 1;
   return maxVal;
}
int FindMaxProductPath(vector<int> graph[], int Size) {
   int maxProd = -10;
   int pathA, pathB;
   int currPathMax, prod;
   for (int i = 0; i < Size; i++) {
      for (int j = 0; j < graph[i].size(); j++){
         currPathMax = 0;
         pathA = TreeTraverse(graph, currPathMax, graph[i][j],i);
         currPathMax = 0;
         pathB = TreeTraverse(graph, currPathMax, i,graph[i][j]);
         prod = (pathA * pathB);
         maxProd = max(maxProd, prod);
      }
   }
   return maxProd;
}
void insertEdge(vector<int> graph[], int val1, int val2){
   graph[val1].push_back(val2);
   graph[val2].push_back(val1);
}
int main(){
   int Size = 8;
   vector<int> graph[Size + 2];
   insertEdge(graph, 1, 2);
   insertEdge(graph, 2, 4);
   insertEdge(graph, 3, 1);
   insertEdge(graph, 5, 4);
   insertEdge(graph, 7, 8);
   insertEdge(graph, 8, 4);
   insertEdge(graph, 5, 6);
   cout<<"Maximum product of two non-intersecting paths of tree is "<<FindMaxProductPath(graph, Size)<<"\n";
   return 0;
}

出力

Maximum product of two non-intersecting paths of tree is 8