इस समस्या में, हमें 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