LeetCode 785 判斷二分圖

給定一個無向圖

graph

，當這個圖為二分圖時傳回

true

。

from typing import *
from collections import defaultdict


class Solution:
    """
    利用染色的方法判斷一個圖是否是二分圖

    """

    def __init__(self):
        self.flag = True
        self.colors = None
        self.graph = None

    def isBipartite(self, graph: List[List[int]]) -> bool:
        num_node = len(graph)
        self.graph = graph
        self.colors = [0] * num_node
        for i in range(num_node):
            if self.colors[i] == 0:
                self.dfs(i, 1)
        return self.flag

    def dfs(self, node, c):
        if not self.flag:
            return
        self.colors[node] = c
        for node1 in self.graph[node]:
            if self.colors[node1] == c:
                self.flag = False
            elif self.colors[node1] == 0:
                self.dfs(node1, -c)