N명의 사람들이 있다고 가정하고(1, 2, ..., N으로 번호가 매겨짐) 모든 사람을 크기에 관계없이 두 개의 하위 그룹으로 나누고 싶습니다. 이제 각 사람은 다른 사람을 싫어할 수 있으며 같은 그룹에 들어가지 않아야 합니다. 따라서 [i] =[a, b]를 싫어하면, b와 번호가 지정된 사람들을 같은 그룹에 넣을 수 없음을 나타냅니다. 이런 식으로 모든 사람을 두 그룹으로 나눌 수 있는지 찾아야 합니다.
따라서 입력이 N =4이고 싫어함 =[[1,2],[1,3],[2,4]]인 경우 출력은 true이고 그룹은 [1,4] 및 [2 ,3].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
그룹이라는 집합의 배열을 생성합니다. 두 개의 그룹이 있을 것입니다.
-
dfs()라는 메서드를 만듭니다. 이 메서드는 노드, 배열 그래프 및 x
를 사용합니다. -
보조 :=1 – x
-
groups[aux]에 노드가 있으면 false를 반환합니다.
-
노드를 그룹에 삽입[x]
-
범위 0에서 그래프[노드] 크기까지의 i에 대해 – 1
-
u :=그래프[노드, i]
-
groups[aux]에 u가 없고 dfs(u, graph, aux)가 false이면 false를 반환합니다.
-
-
그렇지 않으면 true를 반환합니다.
-
주요 방법에서 다음을 수행하십시오 -
-
크기가 [N + 1]인 그래프라는 배열을 만듭니다.
-
범위 0에서 싫어요 크기 - 1
-
u :=싫어함[i, 0], v :=싫어함[i, 1]
-
v를 그래프[u]에 삽입하고 u를 그래프[v]에 삽입
-
-
범위 1에서 N까지의 i에 대해
-
groups[0]에 i가 없고 groups[1]에 i가 없으면
-
dfs(i, graph, 0)이 거짓이면 거짓을 반환
-
-
-
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