CareerCup

#!/usr/bin/python
"""
Solution is incorrect, just realized, if it branches two ways, it follow one path to it's end, and end... (I'm more awake now)

A Lazy Breadth Search approach, retests Nodes it came from. I think it can be improved a bit, just tired to review it A.T.M. 
First time I've done anything graph related in python 
"""

graph_true = {'A': ['B','D'],
              'B': ['A','C'],
              'C': ['B','D'],
              'D': ['A','C','E'],
              'E': ['F','B']} 
def bipartite(graph = None,start = ''):
    if not start:
        return False
    visited = {}
    color = True
    to_visit = list(start)
    for i in xrange(len(graph)):
        for node in to_visit:
            if node in visited:
                if visited[node] != color:
                    return False
            else:
                visited[node] = color
        to_visit[:] = []
        color = not color
        to_visit.extend(graph[node])
    if len(visited) < len(graph):
       return False
    return True

print bipartite(graph_true,'A')

Algorithm:
• Run BFS search and colour all nodes in odd layers red, others blue
• Go through all edges in adjacency list and 
check if each of them has two different 
colours at its ends colours at its ends -if so then if so then G
is bipartite, otherwise it is not

You can implement it using BFS with an additional array colour[], When we add a node to layer L, than set colour[L]=red if  L is even else set colour[L] = blue.
At the end of BFS, just scan all edges, if any edge has same colour than graph is bi-partite.

bool isbipartite(vector<vector<int>>& v) { // adjacency list 
    // suppose G is connected... :P
    int n = v.size();
    //vector<bool> visited(n, false);
    vector<int> color(n, -1); // -1: not visted, valid colors: 0, 1
    color[0] = 0;
    queue<int> q;
    q.push(0);
    while (!q.empty()) { // invariant:bfs+ all the nodes were colored before putting them into the queue
        int curr = q.front(); q.pop();
        for (int j=0;j<v[curr].size();j++) {
            if (color[v[curr][j]] == -1) {
                color[v[curr][j]] = 1-color[curr];
                q.push(v[curr][j]);
            } else if (color[v[curr][j]] == color[curr]) {
                return false;
            }
        }
    }
    return true;
}