এই সমস্যায় একটি অনির্দেশিত সংযুক্ত ট্রি T দেওয়া আছে n নোড সহ। আমাদের C++-এ ট্রিতে দুটি অ-অন্তঃচ্ছেদী পথের সর্বোচ্চ গুণফল বের করার প্রোগ্রাম লিখতে হবে।
সমস্যার বিবরণ - ট্রিতে সব অ-অন্তঃচ্ছেদী পথ বের করে তাদের দৈর্ঘ্যের গুণফলের সর্বোচ্চ মান বের করতে হবে।
উদাহরণ:
ইনপুট
গ্রাফ (চিত্রে দেখুন)
আউটপুট
8
ব্যাখ্যা
বিবেচিত অ-অন্তঃচ্ছেদী পথ: C-A-B (দৈর্ঘ্য ২) এবং F-E-D-G-H (দৈর্ঘ্য ৪)। গুণফল = ৮।
সমাধানের পদ্ধতি
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 "<আউটপুট
Maximum product of two non-intersecting paths of tree is 8
