C++의 트리에서 교차하지 않는 두 경로의 최대 곱

이 문제에서는 n개의 노드가 있는 무방향 연결 트리 T가 주어집니다. 우리의 임무는 C++의 트리에서 교차하지 않는 두 경로의 최대 곱을 찾는 프로그램을 만드는 것입니다.

문제 설명 - 트리에서 교차하지 않는 두 경로의 최대 곱 찾기. 흥미롭지 않은 모든 경로를 찾은 다음 길이의 곱을 찾습니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

그래프 -

출력

8

설명

고려되는 교차하지 않는 경로는 C-A-B입니다. 및 F-E-D-G-H .

길이는 2와 4입니다. 제품 =8입니다.

솔루션 접근 방식

이 문제에 대한 해결책은 DFS를 사용하여 트리를 탐색하는 것입니다. 그리고 연결 모서리를 제거하면 고유한 경로를 찾습니다. 그리고 경로를 반복하고 길이를 찾으십시오. 그런 다음 경로와 쌍을 이루고 길이의 곱을 찾습니다. 둘은 그들의 곱이 최대가 되는 방식으로 고려됩니다.

우리 솔루션 구현을 위한 프로그램

예시

#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