資料結構
網路
關係資料庫管理系統 (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 次瀏覽
