数据结构
网络
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 次浏览
广告