check if a graph is bipartite using depthfirst search dfs args graph adjacency list representing the graph returns true if bipartite false otherwise checks if the graph can be divided into two sets of vertices such that no two vertices within the same set are connected by an edge examples fixme this test should pass isbipartitedfsdefaultdictlist 0 1 2 1 0 3 2 0 4 traceback most recent call last runtimeerror dictionary changed size during iteration isbipartitedfsdefaultdictlist 0 1 2 1 0 3 2 0 1 false isbipartitedfs true isbipartitedfs0 1 3 1 0 2 2 1 3 3 0 2 true isbipartitedfs0 1 2 3 1 0 2 2 0 1 3 3 0 2 false isbipartitedfs0 4 1 2 4 3 4 4 0 2 3 true isbipartitedfs0 1 3 1 0 2 2 1 3 3 0 2 4 0 false isbipartitedfs7 1 3 1 0 2 2 1 3 3 0 2 4 0 traceback most recent call last keyerror 0 fixme this test should fails with keyerror 4 isbipartitedfs0 1 3 1 0 2 2 1 3 3 0 2 9 0 false isbipartitedfs0 1 3 1 0 2 traceback most recent call last keyerror 1 isbipartitedfs1 0 2 0 1 1 1 0 2 2 1 1 true isbipartitedfs0 9 1 3 1 0 2 2 1 3 3 0 2 traceback most recent call last keyerror 0 fixme this test should fails with typeerror list indices must be integers or isbipartitedfs0 1 0 3 0 1 0 0 2 0 2 0 1 0 3 0 3 0 0 2 0 true isbipartitedfsa 1 3 b 0 2 c 1 3 d 0 2 traceback most recent call last keyerror 1 isbipartitedfs0 b d 1 a c 2 b d 3 a c traceback most recent call last keyerror b perform depthfirst search dfs on the graph starting from a node args node the current node being visited color the color assigned to the current node returns true if the graph is bipartite starting from the current node false otherwise check if a graph is bipartite using a breadthfirst search bfs args graph adjacency list representing the graph returns true if bipartite false otherwise check if the graph can be divided into two sets of vertices such that no two vertices within the same set are connected by an edge examples fixme this test should pass isbipartitebfsdefaultdictlist 0 1 2 1 0 3 2 0 4 traceback most recent call last runtimeerror dictionary changed size during iteration isbipartitebfsdefaultdictlist 0 1 2 1 0 2 2 0 1 false isbipartitebfs true isbipartitebfs0 1 3 1 0 2 2 1 3 3 0 2 true isbipartitebfs0 1 2 3 1 0 2 2 0 1 3 3 0 2 false isbipartitebfs0 4 1 2 4 3 4 4 0 2 3 true isbipartitebfs0 1 3 1 0 2 2 1 3 3 0 2 4 0 false isbipartitebfs7 1 3 1 0 2 2 1 3 3 0 2 4 0 traceback most recent call last keyerror 0 fixme this test should fails with keyerror 4 isbipartitebfs0 1 3 1 0 2 2 1 3 3 0 2 9 0 false isbipartitebfs0 1 3 1 0 2 traceback most recent call last keyerror 1 isbipartitebfs1 0 2 0 1 1 1 0 2 2 1 1 true isbipartitebfs0 9 1 3 1 0 2 2 1 3 3 0 2 traceback most recent call last keyerror 0 fixme this test should fails with typeerror list indices must be integers or isbipartitebfs0 1 0 3 0 1 0 0 2 0 2 0 1 0 3 0 3 0 0 2 0 true isbipartitebfsa 1 3 b 0 2 c 1 3 d 0 2 traceback most recent call last keyerror 1 isbipartitebfs0 b d 1 a c 2 b d 3 a c traceback most recent call last keyerror b check if a graph is bipartite using depth first search dfs args graph adjacency list representing the graph returns true if bipartite false otherwise checks if the graph can be divided into two sets of vertices such that no two vertices within the same set are connected by an edge examples fixme this test should pass is_bipartite_dfs defaultdict list 0 1 2 1 0 3 2 0 4 traceback most recent call last runtimeerror dictionary changed size during iteration is_bipartite_dfs defaultdict list 0 1 2 1 0 3 2 0 1 false is_bipartite_dfs true is_bipartite_dfs 0 1 3 1 0 2 2 1 3 3 0 2 true is_bipartite_dfs 0 1 2 3 1 0 2 2 0 1 3 3 0 2 false is_bipartite_dfs 0 4 1 2 4 3 4 4 0 2 3 true is_bipartite_dfs 0 1 3 1 0 2 2 1 3 3 0 2 4 0 false is_bipartite_dfs 7 1 3 1 0 2 2 1 3 3 0 2 4 0 traceback most recent call last keyerror 0 fixme this test should fails with keyerror 4 is_bipartite_dfs 0 1 3 1 0 2 2 1 3 3 0 2 9 0 false is_bipartite_dfs 0 1 3 1 0 2 traceback most recent call last keyerror 1 is_bipartite_dfs 1 0 2 0 1 1 1 0 2 2 1 1 true is_bipartite_dfs 0 9 1 3 1 0 2 2 1 3 3 0 2 traceback most recent call last keyerror 0 fixme this test should fails with typeerror list indices must be integers or is_bipartite_dfs 0 1 0 3 0 1 0 0 2 0 2 0 1 0 3 0 3 0 0 2 0 true is_bipartite_dfs a 1 3 b 0 2 c 1 3 d 0 2 traceback most recent call last keyerror 1 is_bipartite_dfs 0 b d 1 a c 2 b d 3 a c traceback most recent call last keyerror b perform depth first search dfs on the graph starting from a node args node the current node being visited color the color assigned to the current node returns true if the graph is bipartite starting from the current node false otherwise check if a graph is bipartite using a breadth first search bfs args graph adjacency list representing the graph returns true if bipartite false otherwise check if the graph can be divided into two sets of vertices such that no two vertices within the same set are connected by an edge examples fixme this test should pass is_bipartite_bfs defaultdict list 0 1 2 1 0 3 2 0 4 traceback most recent call last runtimeerror dictionary changed size during iteration is_bipartite_bfs defaultdict list 0 1 2 1 0 2 2 0 1 false is_bipartite_bfs true is_bipartite_bfs 0 1 3 1 0 2 2 1 3 3 0 2 true is_bipartite_bfs 0 1 2 3 1 0 2 2 0 1 3 3 0 2 false is_bipartite_bfs 0 4 1 2 4 3 4 4 0 2 3 true is_bipartite_bfs 0 1 3 1 0 2 2 1 3 3 0 2 4 0 false is_bipartite_bfs 7 1 3 1 0 2 2 1 3 3 0 2 4 0 traceback most recent call last keyerror 0 fixme this test should fails with keyerror 4 is_bipartite_bfs 0 1 3 1 0 2 2 1 3 3 0 2 9 0 false is_bipartite_bfs 0 1 3 1 0 2 traceback most recent call last keyerror 1 is_bipartite_bfs 1 0 2 0 1 1 1 0 2 2 1 1 true is_bipartite_bfs 0 9 1 3 1 0 2 2 1 3 3 0 2 traceback most recent call last keyerror 0 fixme this test should fails with typeerror list indices must be integers or is_bipartite_bfs 0 1 0 3 0 1 0 0 2 0 2 0 1 0 3 0 3 0 0 2 0 true is_bipartite_bfs a 1 3 b 0 2 c 1 3 d 0 2 traceback most recent call last keyerror 1 is_bipartite_bfs 0 b d 1 a c 2 b d 3 a c traceback most recent call last keyerror b
from collections import defaultdict, deque


def is_bipartite_dfs(graph: defaultdict[int, list[int]]) -> bool:
    

    def depth_first_search(node: int, color: int) -> bool:
        
        if visited[node] == -1:
            visited[node] = color
            for neighbor in graph[node]:
                if not depth_first_search(neighbor, 1 - color):
                    return False
        return visited[node] == color

    visited: defaultdict[int, int] = defaultdict(lambda: -1)
    for node in graph:
        if visited[node] == -1 and not depth_first_search(node, 0):
            return False
    return True


def is_bipartite_bfs(graph: defaultdict[int, list[int]]) -> bool:
    
    visited: defaultdict[int, int] = defaultdict(lambda: -1)
    for node in graph:
        if visited[node] == -1:
            queue: deque[int] = deque()
            queue.append(node)
            visited[node] = 0
            while queue:
                curr_node = queue.popleft()
                for neighbor in graph[curr_node]:
                    if visited[neighbor] == -1:
                        visited[neighbor] = 1 - visited[curr_node]
                        queue.append(neighbor)
                    elif visited[neighbor] == visited[curr_node]:
                        return False
    return True


if __name__ == "__main":
    import doctest

    result = doctest.testmod()
    if result.failed:
        print(f"{result.failed} test(s) failed.")
    else:
        print("All tests passed!")