讨论/《深度优先搜索》 - 练习:可能的二分法/
《深度优先搜索》 - 练习:可能的二分法
共 2 个回复
class Solution:
    def possibleBipartition(self, N: int, ds: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        for u, v in ds:
            graph[u].append(v)
            graph[v].append(u)
        color = {}
        def dfs(cur, c = 0):
            if cur in color:
                return color[cur] == c
            color[cur] = c
            for nxt in graph[cur]:
                if not dfs(nxt, c ^ 1):
                    return False
            return True
            #  return all(dfs(nxt, c ^ 1) for nxt in graph[cur]) 
        for cur in range(1, N+1):
            if cur not in color and not dfs(cur):
                return False 
        return True
        #  return all(dfs(cur) for cur in range(1, N+1) if cur not in color)
1
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for pre,nt in dislikes:
            graph[pre].append(nt)
            graph[nt].append(pre)
        colordict = defaultdict(int)
        def dfs(i,color) -> bool:
            # 首先对当前的点进行染色
            if colordict[i] == 0:
                colordict[i] = color
            # 遍历图中节点
            for node in graph[i]:
                if colordict[node] == 0 and not dfs(node,-color):
                    return False
                else:
                    if colordict[node] == color:
                        return False
            # 在遍历完成后
            return True
        for i in range(N):
            if colordict[i] == 0 and not dfs(i,1):
                return False
        return True