2022.3.26 图论——判断二分图 II

一、今日刷题

1.题目2.分析3.代码 总结

可能的二分法

跳转LeetCode

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

参考文章

其实这题考察的就是二分图的判定：

如果你把每个人看做图中的节点，相互讨厌的关系看做图中的边，那么 dislikes 数组就可以构成一幅图；

又因为题目说互相讨厌的人不能放在同一组里，相当于图中的所有相邻节点都要放进两个不同的组；

那就回到了「双色问题」，如果能够用两种颜色着色所有节点，且相邻节点颜色都不同，那么你按照颜色把这些节点分成两组不就行了嘛。

所以解法就出来了，我们把 dislikes 构造成一幅图，然后执行二分图的判定算法即可

答案代码：

package Graph;

import java.util.linkedList;
import java.util.List;


public class PossibleBipartition {
    public static void main(String[] args) {
        int[][] dislikes = {{1, 2}, {1, 3}, {2, 4}};
        PossibleBipartition bipartition = new PossibleBipartition();
        boolean ans = bipartition.possibleBipartition(4, dislikes);
        System.out.println(ans);
    }

    public boolean possibleBipartition(int n, int[][] dislikes) {
        //节点的范围为 0 ~ n，所以数组最大的角标应为 n，故设数组长度为 n + 1
        color = new boolean[n + 1];
        visited = new boolean[n + 1];
        //以下代码调用方法的顺序也对应着我们编写方法的顺序：构图 → 遍历
        //调用构图方法，输入的是二维数组，很像之前遇到的prerequisites啊啥的，本质上都是两节点存储临界关系的数组
        List[] graph = buildGraph(n, dislikes);
        //从节点1开始，从而将遍历函数应用到它的所有邻接节点，直至将所有节点遍历之后，返回存储“判断是否为二分图”的布尔型变量
        for (int i = 1; i <= n; i++) {
            if (visited[i] == false) {
                traverse(graph, i);
            }
        }
        return bipartite;
    }

    private List[] buildGraph(int n, int[][] dislikes) {
        //节点的范围为 0 ~ n，所以数组最大的角标应为 n，故设数组长度为 n + 1
        List[] graph = new linkedList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new linkedList<>();
        }
        for (int[] edge : dislikes) {
            int pointOne = edge[0];
            int pointTwo = edge[1];
            //由于本题中为无向图，故需将相邻的节点都加入彼此的邻接表中
            //即 「无向图」相当于「双向图」
            graph[pointTwo].add(pointOne);
            graph[pointOne].add(pointTwo);
        }
        return graph;
    }

    private boolean bipartite = true;
    private boolean[] visited;
    private boolean[] color;
    private void traverse(List[] graph, int point) {
        if (bipartite == false) {
            return;
        }
        visited[point] = true;
        for (int neighboursOfPoint : graph[point]) {
            if (visited[neighboursOfPoint] == false) {
                color[neighboursOfPoint] = !color[point];
                traverse(graph, neighboursOfPoint);
            } else {
                if (color[neighboursOfPoint] == color[point]) {
                    bipartite = false;
                }
            }
        }
    }
}

注意 buildGraph 方法中构造集合数组的代码：
一开始不知道这个 linkedList 是哪来的，但参考整型数组的声明：

int[] nums = new int[n];

明白了，linkedList 是在构建 List 集合（自己理解的，不一定对，百度搜不到）。
所以，将 linkedList 换成 ArrayList 也ok。

List[] graph = new linkedList[n + 1];
for (int i = 1; i <= n; i++) {
    graph[i] = new linkedList<>();
}