假设我们有一组N个人（编号分别为1、2，...，N），我们希望将每个人分成任意大小的两个子组。现在每个人都可能不喜欢其他人，因此不应将他们归为一类。因此，如果dislikes [i] = [a，b]，则表明不允许将编号为a和b的人员放入同一组。我们必须找到是否可以通过这种方式将每个人分为两组。
因此，如果输入像N = 4而不喜欢= [[1,2 ,, [1,3]，[2,4]]，则输出为true，该组将为[1,4]和[2 ，3]。
为了解决这个问题，我们将遵循以下步骤-
创建一组称为组的数组，将有两个组
创建一个名为的方法dfs()，它将使用节点，数组图和x
辅助：= 1 – x
如果groups [aux]具有节点，则返回false
将节点插入组[x]
对于i，范围为0到graph [node]的大小– 1
u：= graph [node，i]
如果groups [aux]没有u并且dfs(u,graph,aux)为false，则返回false
否则返回true
从主要方法中执行以下操作-
制作一个大小为[N + 1]的图的数组
对于0到不喜欢的人数范围内的我-1
u：=不喜欢[i，0]，v：=不喜欢[i，1]
将v插入graph [u]并将u插入graph [v]
当我的范围是1到N
如果dfs(i,graph,0)为false，则返回false
如果groups [0]不包含i，groups [1]不包含i，则
返回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