785. Is Graph Bipartite?

https://leetcode.com/problems/is-graph-bipartite/

Python

Color by DFS

二分圖(Bipartite)經典題目

• Time: O(N+E) # N: nodes count; E: edges count
• Space: O(N) # color mapper

class Solution:
    def isBipartite(self, graph):
        color = {}
        for node in range(len(graph)):
            if node in color:
                continue

            stack = [node]
            color[node] = 0

            while stack:
                start = stack.pop()
                for target in graph[start]:
                    if target not in color:
                        stack.append(target)
                        color[target] = 0 if color[start] == 1 else 1
                    elif color[target] == color[start]:
                        return False
        return True