数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究用 C++ 求一个图的最大值排列
在这个问题中，我们给定了一个有 N 个节点的图。我们的任务是找出一个修改后的数组最小值的可能的最大值。
对于给定的图，我们有节点的一个排列，它是左边的最小一个节点的诱导数，它们共享一个公共边。
举个例子，理解这个问题：
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
更新日期： 24-Jan-2022
166 次浏览
广告