इस समस्या में, हमें N नोड्स का एक ग्राफ दिया गया है। हमारा कार्य संशोधित सरणी के न्यूनतम मान के अधिकतम संभावित मान को ज्ञात करना है।
ग्राफ के लिए हमारे पास नोड्स का एक क्रमचय है जो उस नोड की संख्या है जिसके बाएं कम से कम 1 नोड है जो एक सामान्य एज साझा करता है।
उदाहरण से समझते हैं:
इनपुट: N = 4, एज = {{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
