# Is Graph Bipartite?

给定图能否二分，即能找出两个集合，使得每个边的两点分别在两个集合。从任意一点开始染色，把它的邻居染成和它对立的颜色，DFS/BFS依次类推。当遇到邻居已经有色且与当前结点颜色相同，说明不可二分。大图里可能有多个联通子图，因此要遍历每个结点检查一遍。

## Code

```cpp
/*
 * @lc app=leetcode id=785 lang=cpp
 *
 * [785] Is Graph Bipartite?
 *
 * https://leetcode.com/problems/is-graph-bipartite/description/
 *
 * algorithms
 * Medium (44.36%)
 * Likes:    817
 * Dislikes: 103
 * Total Accepted:    62K
 * Total Submissions: 138.2K
 * Testcase Example:  '[[1,3],[0,2],[1,3],[0,2]]'
 *
 * Given an undirected graph, return true if and only if it is bipartite.
 * 
 * Recall that a graph is bipartite if we can split it's set of nodes into two
 * independent subsets A and B such that every edge in the graph has one node
 * in A and another node in B.
 * 
 * The graph is given in the following form: graph[i] is a list of indexes j
 * for which the edge between nodes i and j exists.  Each node is an integer
 * between 0 and graph.length - 1.  There are no self edges or parallel edges:
 * graph[i] does not contain i, and it doesn't contain any element twice.
 * 
 * 
 * Example 1:
 * Input: [[1,3], [0,2], [1,3], [0,2]]
 * Output: true
 * Explanation: 
 * The graph looks like this:
 * 0----1
 * |    |
 * |    |
 * 3----2
 * We can divide the vertices into two groups: {0, 2} and {1, 3}.
 * 
 * 
 * 
 * Example 2:
 * Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
 * Output: false
 * Explanation: 
 * The graph looks like this:
 * 0----1
 * | \  |
 * |  \ |
 * 3----2
 * We cannot find a way to divide the set of nodes into two independent
 * subsets.
 * 
 * 
 * 
 * 
 * Note:
 * 
 * 
 * graph will have length in range [1, 100].
 * graph[i] will contain integers in range [0, graph.length - 1].
 * graph[i] will not contain i or duplicate values.
 * The graph is undirected: if any element j is in graph[i], then i will be in
 * graph[j].
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    bool dfs(int i, bool c, vector<vector<int>> &g, unordered_map<int, bool> &colors) {
        if (colors.count(i)) {
            return colors[i] == c;
        }
        colors[i] = c;
        for (const auto &e : g[i]) {
            if (!dfs(e, !c, g, colors)) return false;
        }
        return true;
    }

    bool isBipartite(vector<vector<int>>& graph) {
        unordered_map<int, bool> colors;
        for (int i = 0; i < graph.size(); ++i) {
            if (!colors.count(i) && !dfs(i, false, graph, colors)) return false;
        } 
        return true;
    }
};
// @lc code=end


```

```java
class Solution {
    public boolean isBipartite(int[][] graph) {
        Map<Integer, Integer> color = new HashMap<>();

        for (int i = 0; i < graph.length; i++) {
            if (!color.containsKey(i) && !dfs(i, 0, graph, color)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(int i, int c, int[][] g, Map<Integer, Integer> color) {
        if (color.containsKey(i)) {
            if (color.get(i) != c) {
                return false;
            }
            return true;
        }
        color.put(i, c);
        for (int nei : g[i]) {
            if (!dfs(nei, c ^ 1, g, color)) {
                return false;
            }
        }

        return true;
    }
}

class Solution {
    public boolean isBipartite(int[][] graph) {
        Map<Integer, Integer> color = new HashMap<>();

        for (int i = 0; i < graph.length; i++) {
            if (!color.containsKey(i) && !bfs(i, graph, color)) {
                return false;
            }
        }
        return true;
    }

    private boolean bfs(int i, int[][] g, Map<Integer, Integer> color) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i);
        int c = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                int val = queue.poll();
                if (color.containsKey(val)) {
                    if (c != color.get(val)) {
                        return false;
                    }
                } else {
                    color.put(val, c);
                    for (int nei : g[val]) {
                        queue.offer(nei);
                    }
                }
            }
            c ^= 1;
        }

        return true;
    }
}
```

## Analysis

时间复杂度O(N + E), 每个节点和边各遍历一次。


---

# 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://hao-fu-1.gitbook.io/oj/graph/bipartition/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.