785. Is Graph Bipartite?

https://leetcode.com/problems/is-graph-bipartite/description/

solution

判断二分图问题: 对图中每个点进行染色。二分图左边的部分置为-1，右边部分全部置为1，那么，任意相邻的两点颜色都不一样

• bfs

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        colors = [0] * len(graph)

        for i in range(len(graph)):  # 注意这里每个点都要遍历一次
            if colors[i] != 0:
                continue
            
            queue = collections.deque()
            queue.append(i)
            colors[i] = 1  # 起始颜色都置为1        

            while queue:
                node = queue.popleft()    

                for adj in graph[node]:
                    if colors[adj] == colors[node]:
                        return False
                    if colors[adj] == 0:
                        colors[adj] = -colors[node]
                        queue.append(adj)
        return True

时间复杂度：O(∣V∣+∣E∣) 空间复杂度：O(∣V∣)

• dfs

follow up

1557. Minimum Number of Vertices to Reach All Nodes

class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        inorder = set()
        for pre, cur in edges:
            inorder.add(cur)
        return [i for i in range(n) if i not in inorder]

886. Possible Bipartition

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        if n == 1 or not dislikes:
            return True

        blue = 1  # color = Eum(1, -1, 0)  # 原始为0    
        graph = collections.defaultdict(list)
        color_dict = collections.defaultdict(int)

        for p1, p2 in dislikes:
            graph[p1].append(p2)
            graph[p2].append(p1)
        
        for i in range(1, n+1):
            if not color_dict[i] and not self.dfs(i, blue, graph, color_dict):
                return False
        return True
    
    def dfs(self, i, color, graph, color_dict):
        color_dict[i] = color
        for nei in graph[i]:
            if color_dict[nei] == color:
                return False
            
            if not color_dict[nei] and not self.dfs(nei, -color, graph, color_dict):
                return False
        return True