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