'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List
from collections import deque
'''
We should be able to greedily color the graph if and only if it is bipartite: 
one node being blue implies all it's neighbors are red, all those neighbors 
are blue, and so on.
'''
class Solution:
    # If we find a neighbor colored the same color as the current node, 
    # then our coloring was impossible.
    # T: O(N+E),  DFS
    # S: O(N), for color_nodes
    def isBipartite(self, graph: List[List[int]]) -> bool:
        colored_nodes = {} # k: node, v: color
        for node in range(len(graph)):
            if node not in colored_nodes:
                stack = [node]
                colored_nodes[node] = 0
                while stack:
                    node = stack.pop()
                    for nei in graph[node]:
                        if nei not in colored_nodes:
                            stack.append(nei)
                            # exclusive or, be different to be true
                            colored_nodes[nei] = colored_nodes[node] ^ 1
                        elif colored_nodes[nei] == colored_nodes[node]:
                            return False
        return True
                     
    
    # BFS
    def isBipartite1(self, graph: List[List[int]]) -> bool:
        colored_nodes = {}
        for node in range(len(graph)):
            if node not in colored_nodes:
                queue = deque([node])
                colored_nodes[node] = 0
                while queue:
                    node = queue.popleft()
                    for nei in graph[node]:
                        if nei not in colored_nodes:
                            queue.append(nei)
                            # exclusive or, be different to be true
                            colored_nodes[nei] = colored_nodes[node] ^ 1
                        elif colored_nodes[nei] == colored_nodes[node]:
                            return False
        return True
    
    
    # DFS function version
    def isBipartite2(self, graph: List[List[int]]) -> bool:
        seen = {}
        for i in range(len(graph)):
            if i not in seen:
                if self.helper(graph, i, 1, seen) == False:
                    return False
        return True
    
    def helper(self, graph, node, color, seen):
        if node in seen:
            if seen[node] != color:
                return False
            return True
        seen[node] = color
        for nei in graph[node]:
            if self.helper(graph, nei, -color, seen) == False:
                return False
        return True
        
        
        
        
        
        
        
        
        
    
                    