785. 判断二分图

题目链接

难度：中等       类型： 二分图、dfs、bfs

示例

解题思路

从任意一个点出发，标颜色（红或绿），当一个节点被标为红色，与其连同的节点将被标为绿色

如果在涂色的过程中，发现一个节点已经被涂过色，且和当前准备涂的颜色不一致，则说明无法二分

代码实现

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        
        NOCOLOR, RED, GREEN = 0, 1, 2
        n = len(graph)
        colors = [NOCOLOR] * n

        def dfs(nodes, color):
            next_color = RED if color == GREEN else GREEN
            for node in nodes:
                if colors[node] == NOCOLOR:
                    colors[node] = next_color
                    if not dfs(graph[node], next_color):
                        return False
                elif colors[node] == next_color:
                    continue
                else:
                    return False
            return True

        for i in range(n):
            if colors[i] == NOCOLOR:
                colors[i] = RED
                if not dfs(graph[i], RED):
                    return False
        return True