Is Graph Bipartite

BFS

visited[node] = 0 # not visited yet
visited[node] = 1 # visited, and the node is in group1
visited[node] = 2 # visited, and the node is in group2

Every time when a current node's neighbor is in the same group as current node, return False.
Otherwise, mark its neighbor group different from its group.

from collections import defaultdict, deque
class Solution(object):
    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """



        q = deque()
        visited = [0 for i in range(len(graph))]


        for i in range(len(graph)):

            if len(graph[i]) == 0 or visited[i] != 0:
                continue

            q.append(i)
            while q:
                for j in range(len(q)):
                    node = q.popleft()
                    for v in graph[node]:
                        if visited[v] == 0:
                            if visited[node] == 1:
                                visited[v] = 2
                            else:
                                visited[v] = 1
                            q.append(v)
                        else:
                            if visited[node] == visited[v]: return False
        return True