Description

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:

graph

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:

graph

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].

Solution

DFS

class Solution {
    public boolean isBipartite(int[][] graph) {
        Set<Integer>[] sets = new HashSet[2];
        for (int i = 0; i < sets.length; ++i) {
            sets[i] = new HashSet<Integer>();
        }
        
        // This graph might be a disconnected graph. So check each unvisited node.
        for (int i = 0; i < graph.length; ++i) {
            if (!dfsIsBipartite(graph, i, sets)) {
                return false;
            }
        }
        
        return true;
    }
    
    public boolean dfsIsBipartite(int[][] graph, int i, Set<Integer>[] sets) {
        return dfsIsBipartite(graph, i, sets, 0) || dfsIsBipartite(graph, i, sets, 1);
    }
    
    public boolean dfsIsBipartite(int[][] graph, int i, Set<Integer>[] sets, int k) {
        if (sets[(k + 1) % 2].contains(i)) {    // i is already in the other set
            return false;
        }
        
        if (sets[k].contains(i)) {      // i is already in the target set
            return true;
        }
        
        sets[k].add(i);
        
        for (int j : graph[i]) {
            // add neighbors to the other set
            if (!dfsIsBipartite(graph, j, sets, (k + 1) % 2)) { 
                sets[k].remove(sets[k].size() - 1);
                return false;
            }
        }
        
        return true;
    }
}

DFS, fill color

用填色法也可以解决：

color

对于每一个连通区来说，以某个节点为开始，默认将其涂成0，然后将它的neighbors涂成1，以此类推，直到节点全被涂完，或者颜色发生碰撞。

注意将起始节点涂成0或者1的结果都是一样的，所以这道题不用backtracking。

class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] colors = new int[graph.length];
        Arrays.fill(colors, -1);
        
        for (int i = 0; i < colors.length; ++i) {
            if (colors[i] != -1) {  // component already colored, don't color again because collision might happen!
                continue;
            }
            
            if (!isValid(graph, i, 0, colors)) {    // color with 0
                return false;
            }
        }
        
        return true;
    }
    
    public boolean isValid(int[][] graph, int i, int c, int[] colors) {
        if (colors[i] != -1) {
            return colors[i] == c;  // color doesn't match
        }
        
        colors[i] = c;
        
        for (int j : graph[i]) {
            if (!isValid(graph, j, 1 - c, colors)) {
                return false;
            }
        }
        
        return true;
    }
}

BFS

可以将填色法用BFS来实现。可以用colors[next] = colors[curr] ^ 1来替代减法。

class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] colors = new int[graph.length];
        Arrays.fill(colors, -1);

        for (int i = 0; i < colors.length; ++i) {
            if (colors[i] != -1) {
                continue;
            }
            
            colors[i] = 0;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            
            while (!queue.isEmpty()) {
                int curr = queue.poll();
                
                for (int next : graph[curr]) {
                    if (colors[next] != -1) {
                        if (colors[next] != (colors[curr] ^ 1)) {   // efficient
                            return false;
                        }
                    } else {
                        colors[next] = colors[curr] ^ 1;
                        queue.offer(next);
                    }
                }
            }
        }
        
        return true;
    }
}