資料結構
網路
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 次瀏覽
廣告