题目描述

给定一组 N 人（编号为 1, 2, ..., N），我们想把每个人分进任意大小的两组。

每个人都可能不喜欢其他人，那么他们不应该属于同一组。

形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。

当可以用这种方法将每个人分进两组时，返回 true；否则返回 false。

样例

输入：N = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]

输入：N = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false

输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false

限制

• 1 <= N <= 2000
• 0 <= dislikes.length <= 10000
• dislikes[i].length == 2
• 1 <= dislikes[i][j] <= N
• dislikes[i][0] < dislikes[i][1]
• 对于 dislikes[i] == dislikes[j] 不存在 i != j。

算法

(二分图判定，黑白染色) $O(n + m)$

1. 用黑白两种颜色对整个图进行染色，相邻的结点染不同的颜色。
2. 如果过程中出现相邻两个结点颜色一样，则说明出现了奇环。
3. 图论告诉我们有奇环的图不是二分图。

时间复杂度

• 需要遍历整个图进行染色，故时间复杂度为 $O(n + m)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储遍历用的数据结构。

C++ 代码 (DFS)

class Solution {
private:
    bool dfs(int u, const vector<vector<int>> &graph, vector<int> &col) {
        for (int v : graph[u])
            if (col[v] == -1) {
                col[v] = 1 - col[u];
                if (!dfs(v, graph, col))
                    return false;
            } else if (col[v] == col[u])
                return false;

        return true;
    }
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(N);
        for (const auto &v : dislikes) {
            int x = v[0] - 1, y = v[1] - 1;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }

        vector<int> col(N, -1);

        for (int i = 0; i < N; i++)
            if (col[i] == -1) {
                col[i] = 0;
                if (!dfs(i, graph, col))
                    return false;
            }

        return true;
    }
};

C++ 代码 (BFS)

class Solution {
private:
    bool bfs(int S, const vector<vector<int>> &graph, vector<int> &col) {
        queue<int> q;

        q.push(S);
        col[S] = 0;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : graph[u]) {
                if (col[v] == col[u])
                    return false;
                if (col[v] == -1) {
                    col[v] = 1 - col[u];
                    q.push(v);
                }
            }
        }

        return true;
    }

public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(N);
        for (const auto &v : dislikes) {
            int x = v[0] - 1, y = v[1] - 1;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }

        vector<int> col(N, -1);

        for (int i = 0; i < N; i++)
            if (col[i] == -1)
                if (!bfs(i, graph, col))
                    return false;

        return true;
    }
};