#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-ii-trees-graphs-dynamic-programming/lc-785-is-graph-bipartite-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-ii-trees-graphs-dynamic-programming/lc-785-is-graph-bipartite-implementation

Repovive

LeetCode 785 Is Graph Bipartite? - Implementation - Coding Patterns II: Trees, Graphs & Dynamic Programming | Google Interview Prep | Repovive

Repovive.

Google Interview Prep6 sections · 128 units7h total

Open in Course

LeetCode 785 Is Graph Bipartite? - Implementation

The code

BFS through each connected component. Assign alternating colors. If a conflict appears, return false.

function isBipartite(graph):
    n = len(graph)
    color = array of size n, filled with -1
    for start from 0 to n-1:
        if color[start] != -1:
            continue
        color[start] = 0
        queue = [start]
        while queue is not empty:
            node = queue.pop_front()
            for neighbor in graph[node]:
                if color[neighbor] == -1:
                    color[neighbor] = 1 - color[node]
                    queue.push(neighbor)
                elif color[neighbor] == color[node]:
                    return false
    return true

$O(V + E)$ time, $O(V)$ space.