এই সমস্যায়, আমাদের N নোডের একটি গ্রাফ দেওয়া হয়েছে। আমাদের কাজ হল পরিবর্তিত অ্যারের ন্যূনতম মানের সর্বাধিক সম্ভাব্য মান খুঁজে বের করা।
গ্রাফের জন্য আমাদের কাছে নোডগুলির একটি স্থানান্তর রয়েছে যা একটি সাধারণ প্রান্ত ভাগ করে এর বাম দিকে ন্যূনতম 1টি নোড সহ প্রবর্তনের সংখ্যা৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : N = 4, edge = {{1, 2}, {2, 3}, {3, 4}, {4, 1}}
Output : 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
