bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets https en wikipedia orgwikibipartitegraph determine if the given graph is bipartite time complexity is oe space complexity is ov divide vertexes in the graph into settype 0 and 1 initialize all settypes as 1 if there is a selfloop it cannot be bipartite set type of u opposite of v determine if the given graph is bipartite time complexity is o e space complexity is o v divide vertexes in the graph into set_type 0 and 1 initialize all set_types as 1 if there is a self loop it cannot be bipartite set type of u opposite of v
def check_bipartite(adj_list):
    

    vertices = len(adj_list)

    
    
    set_type = [-1 for v in range(vertices)]
    set_type[0] = 0

    queue = [0]

    while queue:
        current = queue.pop(0)

        
        if adj_list[current][current]:
            return False

        for adjacent in range(vertices):
            if adj_list[current][adjacent]:
                if set_type[adjacent] == set_type[current]:
                    return False

                if set_type[adjacent] == -1:
                    
                    set_type[adjacent] = 1 - set_type[current]
                    queue.append(adjacent)

    return True