# Leetcode 785. Is Graph Bipartite

判斷一個圖是否為 **二分圖**，可以使用染色法來判斷

## DFS

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # 0 not visited , 1 black , -1 white
        node_length = len(graph)
        color = [0 for i in range(node_length)]
        color_map = {
            1: -1,
            -1: 1
        }

        for current in range(node_length):
            node_color = color[current]
            stack = [current]

            if node_color == 0:
                color[current] = 1 # 如果沒有染色，就先幫他染顏色，黑色或白色都可，因為只要判斷鄰居不相同，即可判斷是不是二分圖
            else: # 已經被染色就跳過
                continue
                
            while stack:
                node = stack.pop()
                neighbors = graph[node]
                for neighbor in neighbors:
                    if color[neighbor] == 0: # 相鄰節點還沒有被染色
                        color[neighbor] = color_map[color[node]]
                        stack.append(neighbor) # 遍歷相鄰節點
                    else: # 檢查是否相同
                        if color[node] == color[neighbor]: # 如果有連接的兩兩節點顏色相同，說明此圖並不是一個二分圖
                            return False
        return True