1.题目

给定一组 n 人（编号为 1, 2, …, n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。

给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和 bi 的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

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

示例 2：
输入：n = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false

示例 3：
输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false

提示：
1 <= n <= 2000
0 <= dislikes.length <= 104
dislikes[i].length == 2
1 <= dislikes[i][j] <= n
ai < bi
dislikes 中每一组都不同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/possible-bipartition

2.思路

（1）二分图
本题与LeetCode_二分图_中等_785. 判断二分图这题十分类似，它们的本质就是二分图的判定，只不过本题需要先通过数组 dislikes 来构建图。

3.代码实现（Java）

//思路1————二分图
class Solution {
    //flag 用于标记该图是否为二分图
    boolean flag = true;
    //color 记录图中节点的颜色，false 和 true 分别代表两种不同的颜色
    boolean[] color;
    //visited 记录图中的节点是否被访问过
    boolean[] visited;

    public boolean possibleBipartition(int n, int[][] dislikes) {
        //初始化，节点编号从 1 开始
        color = new boolean[n + 1];
        visited = new boolean[n + 1];
        //构建图
        List<Integer>[] graph = buildGraph(n, dislikes);
        for (int v = 1; v <= n; v++) {
            if (!visited[v]) {
                DFS(v, graph);
            }
        }
        return flag;
    }

    /*
        利用题目所给信息构建无向图，通过邻接表存储
        其中 n 表示节点个数，dislikes 存储节点之间的关系 
    */
    public List<Integer>[] buildGraph(int n, int[][] dislikes) {
        //图节点编号为 1...n
        List<Integer>[] graph = new LinkedList[n + 1];
        //创建 n 个节点
        for (int i = 1; i <= n; i++) {
            graph[i] = new LinkedList<>();
        }
        //创建节点之间的关系(即无向边)
        for (int[] edge : dislikes) {
            int v = edge[1];
            int w = edge[0];
            //无向图相当于双向图
            // v -> w
            graph[v].add(w);
            // w -> v
            graph[w].add(v);
        }
        return graph;
    }

    public void DFS(int v, List<Integer>[] graph) {
        if (flag == false) {
            return;
        }
        visited[v] = true;
        for (int w : graph[v]) {
            if (visited[w] == false) {
                //节点 w 未被访问过
                color[w] = !color[v];
                DFS(w, graph);
            } else {
                //节点 w 已被访问过
                if (color[w] == color[v]) {
                    flag = false;
                    return;
                }
            }
        }
    }
}