原文链接: https://leetcode-cn.com/problems/is-graph-bipartite

英文原文

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

• There are no self-edges (graph[u] does not contain u).
• There are no parallel edges (graph[u] does not contain duplicate values).
• If v is in graph[u], then u is in graph[v] (the graph is undirected).
• The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

 

Example 1:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2:

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

 

Constraints:

• graph.length == n
• 1 <= n <= 100
• 0 <= graph[u].length < n
• 0 <= graph[u][i] <= n - 1
• graph[u] does not contain u.
• All the values of graph[u] are unique.
• If graph[u] contains v, then graph[v] contains u.

中文题目

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：

• 不存在自环（graph[u] 不包含 u）。
• 不存在平行边（graph[u] 不包含重复值）。
• 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
• 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

如果图是二分图，返回 true ；否则，返回 false 。

 

示例 1：

输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
输出：false
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

示例 2：

输入：graph = [[1,3],[0,2],[1,3],[0,2]]
输出：true
解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。

 

提示：

• graph.length == n
• 1 <= n <= 100
• 0 <= graph[u].length < n
• 0 <= graph[u][i] <= n - 1
• graph[u] 不会包含 u
• graph[u] 的所有值 互不相同
• 如果 graph[u] 包含 v，那么 graph[v] 也会包含 u

通过代码

高赞题解

🙋 今日打卡～

一、什么是二分图

若无向图 $G=(V,E)$ 的顶点集 $V$ 可以分割为两个互不相交的子集，且图中每条边的两个顶点分别属于不同的子集，则称图 $G$ 为一个二分图。

二、判断二分图

1、深度优先搜索 / 广度优先搜索

我们使用图搜索算法从各个连通域的任一顶点开始遍历整个连通域，遍历的过程中用两种不同的颜色对顶点进行染色，相邻顶点染成相反的颜色。这个过程中倘若发现相邻的顶点被染成了相同的颜色，说明它不是二分图；反之，如果所有的连通域都染色成功，说明它是二分图。

2、并查集

我们知道如果是二分图的话，那么图中每个顶点的所有邻接点都应该属于同一集合，且不与顶点处于同一集合。因此我们可以使用并查集来解决这个问题，我们遍历图中每个顶点，将当前顶点的所有邻接点进行合并，并判断这些邻接点中是否存在某一邻接点已经和当前顶点处于同一个集合中了，若是，则说明不是二分图。

三、具体实现

这几种方法都比较简单，注释的很详细，直接看注释就好啦～

解法一：广度优先搜索

[]
class Solution {
    public boolean isBipartite(int[][] graph) {
        // 定义 visited 数组，初始值为 0 表示未被访问，赋值为 1 或者 -1 表示两种不同的颜色。 
        int[] visited = new int[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        // 因为图中可能含有多个连通域，所以我们需要判断是否存在顶点未被访问，若存在则从它开始再进行一轮 bfs 染色。
        for (int i = 0; i < graph.length; i++) {
            if (visited[i] != 0) {
                continue;
            }
            // 每出队一个顶点，将其所有邻接点染成相反的颜色并入队。
            queue.offer(i);
            visited[i] = 1;
            while (!queue.isEmpty()) {
                int v = queue.poll();
                for (int w: graph[v]) {
                    // 如果当前顶点的某个邻接点已经被染过色了，且颜色和当前顶点相同，说明此无向图无法被正确染色，返回 false。
                    if (visited[w] == visited[v]) {
                        return false;
                    }
                    if (visited[w] == 0) {
                        visited[w] = -visited[v];
                        queue.offer(w);
                    }
                }          
            }
        }
        
        return true;
    }
}

解法二：深度优先搜索

[]
class Solution {
    public boolean isBipartite(int[][] graph) {
        // 定义 visited 数组，初始值为 0 表示未被访问，赋值为 1 或者 -1 表示两种不同的颜色。 
        int[] visited = new int[graph.length];
        // 因为图中可能含有多个连通域，所以我们需要判断是否存在顶点未被访问，若存在则从它开始再进行一轮 dfs 染色。
        for (int i = 0; i < graph.length; i++) {
            if (visited[i] == 0 && !dfs(graph, i, 1, visited)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(int[][] graph, int v, int color, int[] visited) {
        // 如果要对某顶点染色时，发现它已经被染色了，则判断它的颜色是否与本次要染的颜色相同，如果矛盾，说明此无向图无法被正确染色，返回 false。
        if (visited[v] != 0) {
            return visited[v] == color;
        }
        
        // 对当前顶点进行染色，并将当前顶点的所有邻接点染成相反的颜色。
        visited[v] = color;
        for (int w: graph[v]) {
            if (!dfs(graph, w, -color, visited)) {
                return false;
            }
        }
        return true;
    }
}

解法三：并查集

[]
class Solution {
    public boolean isBipartite(int[][] graph) {
        // 初始化并查集
        UnionFind uf = new UnionFind(graph.length);
        // 遍历每个顶点，将当前顶点的所有邻接点进行合并
        for (int i = 0; i < graph.length; i++) {
            int[] adjs = graph[i];
            for (int w: adjs) {
                // 若某个邻接点与当前顶点已经在一个集合中了，说明不是二分图，返回 false。
                if (uf.isConnected(i, w)) {
                    return false;
                }
                uf.union(adjs[0], w);
            }
        }
        return true;
    }
}

// 并查集
class UnionFind {
    int[] roots;
    public UnionFind(int n) {
        roots = new int[n]; 
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
    }

    public int find(int i) {
        if (roots[i] == i) {
            return i;
        }
        return roots[i] = find(roots[i]);
    }

    // 判断 p 和 q 是否在同一个集合中
    public boolean isConnected(int p, int q) {
        return find(q) == find(p);
    }

    // 合并 p 和 q 到一个集合中
    public void union(int p, int q) {
        roots[find(p)] = find(q);
    }
}

复杂度分析

上述三种方法，时间复杂度是 $O(N + M)$, 空间复杂度是 $O(N)$，其中 $N$ 是无向图的顶点数，$M$ 是无向图的边数。

四、知识拓展导读

在二分图上，最常见的问题是求 二分图最大匹配/最大独立集。二分图的最大匹配，简单来说就是找到尽可能多的两两匹配的关系。比如说在某场相亲现场，主持人先让所有男生女生都写好自己感兴趣的若干个异性，主持人需要尽可能多的凑一对对男女去约会。

这个问题经典的解法是 匈牙利算法，这块知识超过了面试要求，感兴趣的同学可以自行查阅资料。

说到相亲，还有一个著名的算法叫做 稳定婚姻问题。就是说，主持人的你安排男男女女相亲，如果当前是男 1 和女 2 在一起，男 2 和女 1 在一起，男1更喜欢女1，女1也更喜欢男1，那么他俩就会私奔，你的安排相亲就是 不稳定 的。对于一群男生和女生，你需要给出一个 稳定 的相亲方案。这个有趣的算法，感兴趣的同学可以看下 matrix67 大神对于这个故事的阐述～
什么是算法：如何寻找稳定的婚姻搭配

五、题目拓展

力扣 886.可能的二分法

题目描述： 给定 N 人（编号为 1, 2, …, N），将其分为两组。每个人都可能有不喜欢的人，那么他们不应该属于同一组，当可以用这种方法将这些人分为两组时，返回 true；否则返回 false。

题目分析： 这题实质也是判断是否构成二分图（以每个人为顶点，以“不喜欢”为边，即若 A 不喜欢 B，则在 A 与 B 之间建边）。

力扣 1349. 参加考试的最大学生数

题目描述： 给定一个教室里 n * m 的座位，里面有一些座位是坏的不能坐。你需要安排学生的座位，要求每个学生的左上/右上/左/右都没有其它学生。要求尽可能多的安排学生考试，问最多可以安排几个学生。

提示： 这道题涉及到求 二分图最大独立集，也可以用带状态压缩的动态规划来做。

统计信息

通过次数	提交次数	AC比率
42793	83107	51.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言