এই সমস্যায়, আমাদের N নোডের একটি গ্রাফ দেওয়া আছে। আমাদের কাজ হল মডিফাইড অ্যারেতে মিনিমাম ভ্যালুর ম্যাক্সিমাম পসিবল ভ্যালু বের করা।
গ্রাফের জন্য আমাদের নোডের একটি পারমুটেশন আছে যা বাম দিকে কমপক্ষে ১টি নোড থাকার সংখ্যা যা সkommer এজ শেয়ার করে।
উদাহরণ
সমস্যাটি বুঝতে একটি উদাহরণ নিই:
ইনপুট : N = 4, edge = {{1, 2}, {2, 3}, {3, 4}, {4, 1}}
আউটপুট : 3
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হল ট্রি থেকে এক নোড থেকে শুরু করে এর সব আডজেসেন্ট নোড ভিজিট করা। আমরা নোডের পারমুটেশন বের করব নোডের সাথে কানেক্টেড নোডের সংখ্যা ফর্মুলা দিয়ে।
ফর্মুলা হল:
কম্পোনেন্টের আকার - 1।
উদাহরণ প্রোগ্রাম
আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:
#include <bits/stdc++.h>
using namespace std;
int dfs(int x, vector<int> adjMat[], int visited[]) {
int sz = 1;
visited[x] = 1;
for (auto ch : adjMat[x])
if (!visited[ch])
sz += dfs(ch, adjMat, visited);
return sz;
}
int maxValPermutationGraph(int n, vector<int> adjMat[]) {
int val = 0;
int visited[n + 1] = { 0 };
for (int i = 1; i <= n; i++)
if (!visited[i])
val += dfs(i, adjMat, visited) - 1;
return val;
}
int main() {
int n = 4;
vector<int> adjMat[n + 1] = {{1, 2}, {2, 3}, {3, 4}, {4, 1}};
cout << "The maximum value permutation of a graph is " << maxValPermutationGraph(n, adjMat);
return 0;
}
আউটপুট
The maximum value permutation of a graph is 3
