LC 0785 [M] Is Graph Bipartite? - ALawliet/algorithms GitHub Wiki

prereq: https://github.com/codewithsenpai/algos/wiki/*LC-0323-%5BM%5D-Number-of-Connected-Components-in-an-Undirected-Graph

---

for BFS: draw it as a tree in layers and check if we can find a cycle/cross edge that specifically occurs on the same level layer, if so it is NOT bipartite

---

class Solution:
    def isBipartite(self, G: List[List[int]]) -> bool:
        n = len(G)
        
        visited = set()
        level = dict()
        
        def bfs_detected_cycle_crossedge(i):
            Q = deque([i])
            visited.add(i)
            level[i] = 0 #

            while Q:
                u = Q.popleft()

                for v in G[u]: # neighbors
                    if v not in visited:
                        visited.add(v)
                        level[v] = level[u] + 1 #
                        Q.append(v)
                    else:
                        if level[v] == level[u]: return True # same level has a cross edge

            return False
        
        for i in range(n):
            if i not in visited:
                if bfs_detected_cycle_crossedge(i): return False
        return True

"pair applicants to the most jobs, pair stable marriage"

for DFS: is it possible to color a graph in 2 colors such that adjacent vertices are different colors?

a graph is not bipartite if we detect a single odd-length cycle starting from some v on any connected component: => a cross edge on the same layer (level distance) cross edges on different adj layers are ok

if using DFS back edges that go back to the same level to create odd-length cycles means it is not bipartite

from queue import Queue

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        
        # for this problem, they give you the adj list of neighbors directly, so don't need to create the adj map

        def bfs(v):
            Q = Queue()
            Q.put(v)
            visited.add(v)
            distance[v] = 0

            while not Q.empty():
                node = Q.get()

                for neighbor in graph[node]:
                    if neighbor not in visited:
                        # TREE EDGE
                        visited.add(neighbor)
                        distance[neighbor] = 1 + distance[node]
                        parent[neighbor] = node 
                        Q.put(neighbor)
                    else:
                          if neighbor != parent[node]:
                              # CROSS EDGE = cycle detected
                              if distance[neighbor] == distance[node]:
                                  # same-level cross edge = odd-length cycle = not bipartite
                                  return False
                              # all cross edges were between vertices in adj layers, so it is bipartite

            return True
        
        def dfs(node):
            visited.add(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    color[neighbor] = 1 - color[node]
                    # TREE EDGE
                    parent[neighbor] = node
                    if dfs(neighbor) == False: return False
                        # current parent or some ancestor further up could be a BACK EDGE
                        # => there was a cycle detected in a previous subtree
                else:
                    if node in parent: # now needed for some reason
                        if neighbor != parent[node]:
                            # BACK EDGE = cycle detected
                            if color[neighbor] == color[node]: # ***
                                # back edge that creates odd-length cycle
                                return False
            return True
                        
        
                        
        visited = set()
        parent = dict() # must track the parent to detect cycles: BFS (cross edges), DFS (back edges)
        num_components = 0
        
        distance = dict() # BFS ***
        color = {v: 0 for v in range(n)} # DFS ***

        is_bipartite = bool()
        
        # we must still explore all of the components starting from some v
        # because if ANY connected component is not bipartite, then the graph cannot be bipartite
        # you might have cases where 1 component is bipartite but the next is not

#         for v in range(n):
#             if v not in visited:
#                 # number_of_connected_components += 1
#                 # if number_of_connected_components > 1: return False
                
#                 if (bfs(v) == False): is_bipartite = False
                    
        is_bipartite = not any(bfs(v) == False for v in range(n) if v not in visited)
        # is_bipartite = not any(dfs(v) == False for v in range(n) if v not in visited)

        return is_bipartite