Is Graph Bipartite?

https://leetcode.com/problems/is-graph-bipartite/description/

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

Code

/*
 * @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

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), 每个节点和边各遍历一次。