# 0785. 判断二分图

## 题目地址（785. 判断二分图）

<https://leetcode-cn.com/problems/is-graph-bipartite/>

## 题目描述

```
给定一个无向图 graph，当这个图为二分图时返回 true。

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

graph 将会以邻接表方式给出，graph[i]表示图中与节点 i 相连的所有节点。每个节点都是一个在 0 到 graph.length-1 之间的整数。这图中没有自环和平行边： graph[i]  中不存在 i，并且 graph[i]中没有重复的值。

示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释:
无向图如下:
0----1
| |
| |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释:
无向图如下:
0----1
| \ |
| \ |
3----2
我们不能将节点分割成两个独立的子集。
注意:

graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果 j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。
```

## 前置知识

* 图的遍历
* DFS

## 公司

* 暂无

## 着色法 + DFS

求二分图有两种思路，一个是着色法，另外一个是并查集。

### 思路

和 886 思路一样。 我甚至**直接拿过来 dfs 函数一行代码没改就 AC 了**。

唯一需要调整的地方是 graph 。 我将其转换了一下，具体可以看代码，非常简单易懂。

具体算法：

* 设置一个长度为 N 的数组 colors，colors\[i] 表示 节点 i 的颜色，0 表示无颜色， 1 表示一种颜色， - 1 表示另一种颜色。
* 初始化 colors 全部为 0
* 构图（这里有邻接矩阵） 使得 grid\[i]\[j] 表示 i 和 j 是否有连接（这里用 0 表示无， 1 表示有）
* 遍历图。
  * 如果当前节点未染色，则染色，不妨染为颜色 1
  * 递归遍历其邻居
    * 如果邻居没有染色， 则染为另一种颜色。即 color \* - 1，其中 color 为当前节点的颜色
    * 否则，判断当前节点和邻居的颜色是否一致，不一致则返回 False，否则返回 True

强烈建议两道题一起练习一下。

### 关键点

* 图的建立和遍历
* colors 数组

### 代码

```python
class Solution:
    def dfs(self, grid, colors, i, color, N):
        colors[i] = color
        for j in range(N):
            if grid[i][j] == 1:
                if colors[j] == color:
                    return False
                if colors[j] == 0 and not self.dfs(grid, colors, j, -1 * color, N):
                    return False
        return True

    def isBipartite(self, graph: List[List[int]]) -> bool:
        N = len(graph)
        grid = [[0] * N for _ in range(N)]
        colors = [0] * N
        for i in range(N):
            for j in graph[i]:
                grid[i][j] = 1
        for i in range(N):
            if colors[i] == 0 and not self.dfs(grid, colors, i, 1, N):
                return False
        return True
```

**复杂度分析**

令 v 和 e 为图中的顶点数和边数。

* 时间复杂度：$O(v+e)$
* 空间复杂度：$O(v)$, stack depth = $O(v)$, and colors array.length = $O(v)$

如上代码并不优雅，之所以这么写只是为了体现和 886 题一致性。一个更加优雅的方式是不建立 grid，而是利用题目给的 graph（邻接矩阵）。

```python
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        colors = [0] * n
        def dfs(i, color):
            colors[i] = color
            for neibor in graph[i]:
                if colors[neibor] == color: return False
                if colors[neibor] == 0 and not dfs(neibor,-1*color): return False
            return True
        for i in range(n):
            if colors[i] == 0 and not dfs(i,1): return False
        return True
```

## 并查集

### 思路

遍历图，对于每一个顶点 i，将其所有邻居进行合并，合并到同一个联通域中。这样当发现某个顶点 i 和其邻居已经在同一个联通分量的时候可以直接返回 false，否则返回 true。

### 代码

代码支持：Python3，Java

Python3 Code：

```python
class UF:
    def __init__(self, n):
        self.parent = {}
        for i in range(n):
            self.parent[i] = i
    def union(self, i,j):
        self.parent[self.find(i)] = self.find(j)
    def find(self, i):
        if i == self.parent[i]: return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
    def is_connected(self, i,j):
        return self.find(i) == self.find(j)

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        uf = UF(n)
        for i in range(n):
            for neibor in graph[i]:
                if uf.is_connected(i, neibor): return False
                uf.union(graph[i][0], neibor)
        return True
```

Java Code：

```java
// weighted quick-union with path compression
class Solution {
    class UF {
        int numOfUnions; // number of unions
        int[] parent;
        int[] size; 

        UF(int numOfElements) {
            numOfUnions = numOfElements;
            parent = new int[numOfElements];
            size = new int[numOfElements];
            for (int i = 0; i < numOfElements; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        // find the head/representative of x
        int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]]; 
                x = parent[x];     
            }
            return x;
        }

        void union(int p, int q) {
            int headOfP = find(p);
            int headOfQ = find(q);
            if (headOfP == headOfQ) {
                return;
            }
            // connect the small tree to the larger tree
            if (size[headOfP] < size[headOfQ]) {
                parent[headOfP] = headOfQ; // set headOfP's parent to be headOfQ 
                size[headOfQ] += size[headOfP];
            } else {
                parent[headOfQ] = headOfP;
                size[headOfP] += size[headOfQ];
            }
            numOfUnions -= 1;
        }

        boolean connected(int p, int q) {
            return find(p) == find(q);
        }
    }

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        UF unionfind = new UF(n);
        // i is what node each adjacent list is for
        for (int i = 0; i < n; i++) {
            // i's neighbors
            for (int neighbor : graph[i]) {
                // i should not be in the union of its neighbors
                if (unionfind.connected(i, neighbor)) {
                    return false;
                }
                // add into unions
                unionfind.union(graph[i][0], neighbor);
            }
        }

        return true;
    }
```

**复杂度分析**

令 v 和 e 为图中的顶点数和边数。

* 时间复杂度：$O(v+e)$, using weighted quick-union with path compression, where union, find and connected are $O(1)$, constructing unions takes $O(v)$
* 空间复杂度：$O(v)$ for auxiliary union-find space int\[] parent, int\[] space

## 相关问题

* [886. 可能的二分法](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/886.possible-bipartition)

更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/785.is-graph-bipartite.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.