886. Possible Bipartition ---M ！！

We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

 

Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true 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: The first group has [1,4], and the second group has [2,3].

Example 2:

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.

 

Constraints:

• 1 <= n <= 2000
• 0 <= dislikes.length <= 104
• dislikes[i].length == 2
• 1 <= ai < bi <= n
• All the pairs of dislikes are unique.

 A:

----------BFS---------  用queue------------

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<int> Color(n + 1, -1);
        queue<int> Q;
        vector<vector<int>> V(n + 1, vector<int>());
        for (auto ab : dislikes) {
            V[ab[0]].push_back(ab[1]);
            V[ab[1]].push_back(ab[0]);
        }
        for (int i = 1; i <= n; i++) {
            if (Color[i] >= 0)
                continue;
            Color[i] = 0; // assign a random color 0 or 1
            Q.push(i);
            while (not Q.empty()) {
                auto a = Q.front();
                Q.pop();
                for (auto b : V[a]) {
                    if (Color[b] >= 0) {
                        if (Color[b] == Color[a])
                            return false;
                    } else {
                        Color[b] = 1 - Color[a];
                        Q.push(b);
                    }
                }
            }
        }
        return true;
    }
};

Mistakes：

为什么这个dislike是bidirectional的呢？ 题意里面并没有看出来呀。 

 （但是不那样，就pass 不了）