785. Is Graph Bipartite?

Given an undirected graph, returntrueif 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 jfor which the edge between nodes iand jexists. Each node is an integer between 0and 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:

• graphwill have length in range [1, 100].

• graph[i]will contain integers in range[0, graph.length - 1].

• graph[i]will not contain ior duplicate values.

• The graph is undirected: if any element jis in graph[i], then iwill be in graph[j].

Thoughts:

1. DFS: color each node:

   1. for each node, first check if it has been colored, if is, return current color value == color to be added

   2. color the node

   3. try color all of its neightbor with different value, if failed, returned false; else return true

2. BFS: we need to check each if each cluster(edges linked together) is Bipartite. By shawntsai at here

Code: BFS T:(V+E); S: O(E): ( For a directed graph, the sum of the sizes of the adjacency lists of all the nodes is E (total number of edges). So, the complexity of DFS is O(V) + O(E) = O(V + E); for an undirected graph, each edge will appear twice. Once in the adjacency list of either end of the edge. So, the overall complexity will be O(V) + O (2E) ~ O(V + E).)

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

        for (int i = 0; i < n; i++) {              //This graph might be a disconnected graph. So check each unvisited node.
            if (colors[i] == -1 && !validColor(graph, colors, 0, i)) {
                return false;
            }
        }
        return true;
    }

    public boolean validColor(int[][] graph, int[] colors, int color, int node) {
        if (colors[node] != -1) {
            return colors[node] == color;
        }       
        colors[node] = color;       
        for (int next : graph[node]) {
            if (!validColor(graph, colors, 1 - color, next)) {
                return false;
            }
        }
        return true;
    }
}

Code: BFS T:(V+E); S:O(V)

class Solution {
    public boolean isBipartite(int[][] graph) {
        //BFS
        // 0(not meet), 1(black), 2(white)
        int[] colors = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if (graph[i].length != 0 && colors[i] == 0) {
                colors[i] = 1;
                // BFS
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);
                while(! q.isEmpty()) {
                    int cur = q.poll();
                    for (int v: graph[cur]) { // expand its neighbor
                        if (colors[v] == 0) {
                            colors[v] = (colors[cur] == 1) ? 2 : 1;
                            q.offer(v);
                        } else {
                            if (colors[v] == colors[cur]) return false;
                        }
                    }
                }                        
            }
        }
        return true;
    }
}