class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # 0 means not classified, 1 means group 1, and 2 means group 2
        group = [0] * len(graph)
        v = [0] * len(graph)

        stack = [i for i in range(len(graph))]

        while stack:
            cur = stack.pop()
            if v[cur] == 1:
                continue
            v[cur] = 1
            if group[cur] == 0:
                group[cur] = 1
            
            another = 2 if group[cur] == 1 else 1
            for neighbor in graph[cur]:
                if group[neighbor] == 0:
                    group[neighbor] = another
                    stack.append(neighbor)
                elif group[neighbor] == group[cur]:
                    return False
        return True

相關文章