# Warm Up: Bipartite Graph
The basic idea of this algorithm is to do a DFS of the graph, coloring nodes blue or yellow as we go along. We alternate coloring blue and yellow and if we ever see a neighbor the same color as a node, we return false. If we color the graph to completion, it is a bipartite graph.

### Python Solution

def isBipartite(graph):
    color = {}
    for i in range(len(graph)):
	if i not in color:
	    color[i] = 0
	    if not dfs(i, graph, color):
		    return False
    return True

def dfs(pos, graph, color):
    for i in graph[pos]:
        if i in color:
            if color[i] == color[pos]:
                return False
        else:
            color[i] = 1 - color[pos]
            if not dfs(i, graph, color):
                return False
    return True

### Java Solution

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

        //This graph might be a disconnected graph.
        //So check each unvisited node.
        for (int i = 0; i < n; i++) {
            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;
    }
}

###### tags: `Week 5-Graphs`