785. Is Graph Bipartite?

Tags:

• Medium
• graph
• bfs
• recommend
• graph coloring

Link

Graph coloring problem, make sure every adjacency vertex are in different group

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:

        Groups = {}

        for i in range(len(graph)):
            if i not in Groups:
                Groups[i] = 1
            dq = deque([i])

            while dq:
                lens = len(dq)
                for _ in range(lens):
                    idx = dq.popleft()

                    for ii in graph[idx]:
                        if ii not in Groups:
                            Groups[ii] = -Groups[idx]
                            dq.append(ii)
                        elif Groups[ii] != -Groups[idx]:
                            return False

        return True