数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 中可能的二分图
假设我们有一组 N 个人（他们编号为 1, 2, ..., N），我们想把每个人分成任意大小的两个子组。现在每个人可能不喜欢某些其他人，他们不应该在同一个组中。所以，如果 dislikes[i] = [a, b]，这意味着不允许将编号为 a 和 b 的人放在同一个组中。我们必须找到是否可以这样将每个人分成两组。
所以如果输入像 N = 4 且 dislike = [[1,2],[1,3],[2,4]]，输出将为 true，组将为 [1,4] 和 [2,3]。
为了解决这个问题，我们将遵循以下步骤：
创建一个名为 groups 的集合数组，将有两个组。
创建一个名为 dfs() 的方法，它将接收节点、一个数组图和 x。
aux := 1 – x
如果 groups[aux] 包含节点，则返回 false。
将节点插入 groups[x]。
对于范围从 0 到 graph[node] 大小 - 1 的 i
u := graph[node, i]
如果 groups[aux] 不包含 u 且 dfs(u, graph, aux) 为 false，则返回 false。
否则返回 true。
从主方法执行以下操作：
创建一个名为 graph 的大小为 [N + 1] 的数组。
对于范围从 0 到 dislikes 大小 - 1 的 i
u := dislikes[i, 0], v := dislikes[i, 1]
将 v 插入 graph[u] 并将 u 插入 graph[v]。
对于范围从 1 到 N 的 i
如果 groups[0] 不包含 i 且 groups[1] 不包含 i，则
如果 dfs(i, graph, 0) 为 false，则返回 false。
返回 true。
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
set <int> groups[2];
bool dfs(int node, vector <int> graph[], int x){
int aux = 1 - x;
if(groups[aux].count(node)) return false;
groups[x].insert(node);
for(int i = 0; i < graph[node].size(); i++){
int u = graph[node][i];
if(!groups[aux].count(u) && !dfs(u, graph, aux)) return false;
}
return true;
}
bool possibleBipartition(int N, vector<vector<int<<& dislikes) {
vector <int> graph[N + 1];
for(int i = 0; i < dislikes.size(); i++){
int u = dislikes[i][0];
int v = dislikes[i][1];
graph[u].push_back(v);
graph[v].push_back(u);
}
for(int i = 1; i <= N;i++){
if(!groups[0].count(i) && !groups[1].count(i)){
if(!dfs(i, graph, 0)) return false;
}
}
return true;
}
};
main(){
vector<vector<int>> v = {{1,2},{1,3},{2,4}};
Solution ob;
cout << (ob.possibleBipartition(4, v));
}输入
4 [[1,2],[1,3],[2,4]]
输出
true
185 次浏览
