Given a set of N
people (numbered 1, 2, ..., N
), we would like to split everyone into two groups of any size.
Each person may dislike some other people, and they should not go into the same group.
Formally, if dislikes[i] = [a, b]
, it means it is not allowed to put the people numbered a
and b
into the same group.
Return true
if and only if it is possible to split everyone into two groups in this way.
Example 1:
Input: N = 4, dislikes = [[1,2],[1,3],[2,4]] Output: true Explanation: group1 [1,4], group2 [2,3]
Example 2:
Input: N = 3, dislikes = [[1,2],[1,3],[2,3]] Output: false
Example 3:
Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] Output: false
Constraints:
1 <= N <= 2000
0 <= dislikes.length <= 10000
dislikes[i].length == 2
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
- There does not exist
i != j
for whichdislikes[i] == dislikes[j]
.
A:
----------BFS--------- 用queue
class Solution { public: bool possibleBipartition(int N, vector<vector<int>>& dislikes) { vector<int> V(N+1, -1); // -1 undecided, 0, one color, 1 another unordered_map<int, vector<int>> M; for(auto dis : dislikes){ int a = dis[0]; int b = dis[1]; M[a].push_back(b); M[b].push_back(a); } for(int i =1;i<=N; i++){ if(V[i] >=0 ) continue; queue<int> Q; V[i] = 0; Q.push(i); while(!Q.empty()){ int a = Q.front(); Q.pop(); for(auto end : M[a]){ if(V[end]==V[a]){ return false; }else if(V[end]==-1){ V[end] = 1-V[a]; Q.push(end); } } } } return true; } };
No comments:
Post a Comment