LC785.判断二分图 LeetCode 785

方法一： BFS + 染色

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # BFS
        from collections import deque
        n = len(graph)
        
        UNCOLORED, RED, GREEN = 0, 1, 2
        color = [UNCOLORED]*n  # 暂时标记为颜色0
        # 颜色： 0 代表未被涂色
        q = deque()
        q.append(0)
        color[0] = RED
        round_cnt = 0
        for i in range(n):
            if color[i] == UNCOLORED:
                q.append(i)
            while q:
                round_cnt +=1
                for _ in range(len(q)):
                    cur_node = q.popleft()
                    color_next = GREEN if color[cur_node] == RED else RED
                    for next_i in graph[cur_node]:
                        if color[next_i] == UNCOLORED:
                            color[next_i] = color_next
                            q.append(next_i)
                        elif color[next_i] != color_next:
                            return False  
        return True

方法二： DFS + 染色

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # DFS

        n = len(graph)
        UNCOLORED, RED, GREEN = 0, 1, 2
        color = [UNCOLORED]*n  # 暂时标记为颜色0
        # 颜色： 0 代表未被涂色
        res = True
        def dfs(x, color_cur):
            nonlocal res
            color[x] = color_cur
            color_next = GREEN if color[x] == RED else RED
            for next_i in graph[x]:
                if color[next_i] == UNCOLORED:
                    color[next_i] = color_next
                    dfs(next_i, color_next)
                    if res == False:
                        return
                elif color[next_i]!=color_next:
                    res =  False
                    return 
            #return True
        for i in range(n):
            if color[i] == UNCOLORED:
                dfs(i, RED)
                if res == False:
                    break
        return res

方法三：并查集

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]
        self.rank = [1]*n 
        self.cnt = n 
    def find(self, x):
        if x == self.root[x]:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x]>self.rank[root_y]:
                self.root[root_y] = root_x
            elif self.rank[root_y] >self.rank[root_x]:
                self.root[root_x] = root_y 
            else:
                self.root[root_y] = root_x
                self.rank[root_x]+=1
    def isConnected(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # 并查集
        n = len(graph)
        
        uf = UnionFind(n)
        for i in range(n):
            for next_i in graph[i]:
                if uf.isConnected(i, next_i):
                    return False
                uf.union(graph[i][0], next_i) # 注意这里用的是和next_i “同组”的第一个节点，不能用i， 即uf.union(i, next_i)是错误的
        return True