leetcode-graph

785. Is Graph Bipartite.py

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        """
        1st approach: BFS + nodes coloring
        
        Graph is already in adjacency list representation
        
        Given n nodes and edge list of undirected graph, to see if nodes in the graph could be colored using two colors so that there are no adjacent nodes with the same color.
        
        seeh hashmap: index is node, corresponding value is color (1: blue, -1: red)
        
        T: O(n+m)
        S: O(n+m)
        """
        def bfs(graph, start, seen):
            q = collections.deque([(start, 1)]) # (any starting node, color with blue)
            while len(q) > 0:
                cur_node, color = q.popleft()
                if cur_node in seen:
                    if seen[cur_node] != color:
                        return False
                    continue
                seen[cur_node] = color
                for nei_node in graph[cur_node]:
                    # use opposite color to color nei_node
                    q.append((nei_node, -color))
            return True
        
        seen = {}
        n = len(graph)
        for i in range(n):
            if i not in seen:
                if bfs(graph, i, seen) == False:
                    return False
        return True
    
    def isBipartite(self, graph: List[List[int]]) -> bool:

        """
        1st approach: BFS + nodes coloring
        
        Graph is already in adjacency list representation
        
        Given n nodes and edge list of undirected graph, to see if nodes in the graph could be colored using two colors so that there are no adjacent nodes with the same color.
        
        visited array: index is node, corresponding value is color (1: blue, -1: red, 0: haven't visited yet)
        """
        def bfs(graph, start, visited):
            q = collections.deque([(start, 1)]) # (any starting node, color with blue)
            while len(q) > 0:
                cur_node, color = q.popleft()
                if visited[cur_node] != 0:
                    if visited[cur_node] != color:
                        return False
                    continue
                visited[cur_node] = color
                for nei_node in graph[cur_node]:
                    # use opposite color to color nei_node
                    q.append((nei_node, -color))
            return True
        
        n = len(graph)
        visited = [0 for _ in range(n)] # Initially, 0 means having visited yet
        for i in range(n):
            if visited[i] == 0:
                if bfs(graph, i, visited) == False:
                    return False
        return True