题目描述

给定一组 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)$

这题目我想吐槽下，leetcode对于边数给的范围很不准，题目说边集dislikes.length <= 10000，but，我用了Y总的静态链表存储图。e，next两个数组要开330000左右大小才能AC，感觉不合理啊！

思路倒是不难，染色法判定二分图
- 当且仅当图中不含有奇数环，两个集合内部的内部没有边。
- 用黑(1)白(2)两种颜色对整个图进行染色，相邻的结点染不同的颜色。
- 如果过程中出现相邻两个结点颜色一样，则说明出现了奇环。

Java 代码

class Solution {
    static int n;
    static int m;
    static int N = 2009;
    static int M = 330000;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] next = new int[M];
    static int idx = 0;
    static int[] colors = null;

    public static void add(int a, int b) {
        e[idx] = b;
        next[idx] = h[a];
        h[a] = idx++;
    }

    //dfs(u,c)表示把u号点染色成c颜色，并且判断从u号点开始染其他相连的点是否成功
    public static boolean dfs(int u, int newColor) {
        colors[u] = newColor;
        for (int i = h[u]; i != -1; i = next[i]) {
            int j = e[i];
            if (colors[j] == 0) {
                if (!dfs(j, 3 - newColor)) {
                    return false;
                }
            } else if (colors[j] == newColor) {
                return false;//颜色重复
            }
        }
        return true;
    }

    public static boolean possibleBipartition(int N, int[][] dislikes) {
        colors = new int[N + 1];
        n = N;
        Arrays.fill(h, -1);
        for (int[] d : dislikes) {
            int a = d[0];
            int b = d[1];
            add(a, b);
            add(b, a);
        }

        boolean flag = true;//标记是否染色成功
        // 因为图中可能含有多个连通域，所以我们需要判断是否存在顶点未被访问，若存在则从它开始再进行一轮 dfs 染色。
        for (int v = 1; v <= N; v++) {
            if (colors[v] == 0) {
                // 染成1号颜色
                if (!dfs(v, 1)) {
                    flag = false;
                    break;
                }
            }
        }
        return flag;
    }
}