class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        #The Bipartite graph here is different from the strictly defined Bipartite graph in graph theory
        #In graph theory, the partite graph should be a connection graph. 
        #However, the partitie graph here only requires the connected two nodes have different colors.
        #The the problem is relative easy. It is similar to number of island.
        #BFS + memorization
        #TS: O(number of nodes)
        #SC: max O(number of nodes)


        visited = collections.defaultdict(int)

        for node in range(len(graph)):
            if visited[node] > 0:
                continue
            Q = collections.deque([node])
            visited[node] = 1
            while Q:
                start = Q.pop()

                for end in graph[start]:
                    if visited[end] != 0:
                        if visited[end] == visited[start]:
                            return False
                        else:
                            continue
                    if visited[start] == 1:
                        visited[end] = 2
                    elif visited[start] == 2:
                        visited[end] = 1

                    Q.append(end)

        return True