資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
服裝學
法學C++ 程式用於計算可在給定條件下的圖中進行的最大可能劃分
假設我們有一個圖 G 的鄰接矩陣。我們必須檢查是否可以將頂點劃分為非空集合 V1、... Vk，以便：每條邊連線屬於兩個相鄰集合的兩個頂點。如果答案是肯定的，我們必須在這樣的劃分中找出集合 k 的最大可能值。
因此，如果輸入如下
| 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
則輸出將為 4
步驟
為了解決這個問題，我們將遵循以下步驟 -
Define an array dp of size: 210. n := size of matrix fl := 1 ans := 0 for initialize i := 0, when i < n and fl is non-zero, update (increase i by 1), do: fill dp with -1 dp[i] := 0 Define one queue q insert i into q while (q is not empty), do: x := first element of q delete element from q for initialize j := 0, when j < n, update (increase j by 1), do: if matrix[x, j] is same as 1, then: if dp[j] is same as -1, then: dp[j] := dp[x] + 1 insert j into q otherwise when |dp[j] - dp[x]| is not equal to 1, then: fl := 0 for initialize j := 0, when j < n, update (increase j by 1), do: ans := maximum of ans and dp[j] if fl is same as 0, then: return -1 Otherwise return ans + 1
示例
讓我們看看以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> matrix){
int dp[210];
int n = matrix.size();
int fl = 1;
int ans = 0;
for (int i = 0; i < n && fl; i++){
memset(dp, -1, sizeof(dp));
dp[i] = 0;
queue<int> q;
q.push(i);
while (!q.empty()){
int x = q.front();
q.pop();
for (int j = 0; j < n; j++){
if (matrix[x][j] == 1){
if (dp[j] == -1){
dp[j] = dp[x] + 1;
q.push(j);
}
else if (abs(dp[j] - dp[x]) != 1)
fl = 0;
}
}
}
for (int j = 0; j < n; j++)
ans = max(ans, dp[j]);
}
if (fl == 0){
return -1;
}else{
return ans + 1;
}
}
int main(){
vector<vector<int>> matrix = { { 0, 1, 0, 1, 1, 0 }, { 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0 } };
cout << solve(matrix) << endl;
}輸入
{ { 0, 1, 0, 1, 1, 0 }, { 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0 } }輸出
4
更新於： 02-3 月 - 2022
113 次瀏覽
廣告