Graph Theory37 sections · 1633 units
Open in Course

LeetCode 886 Possible Bipartition - Implementation

The code

Here is the full solution:

function possibleBipartition(n, dislikes):
    graph := array of n + 1 empty lists
    for [a, b] in dislikes:
        graph[a].append(b)
        graph[b].append(a)
    color := array of size n + 1, all -1
    for i from 1 to n:
        if color[i] = -1 then
            if not bfs(i, graph, color) then
                return false
    return true

This runs in O(V+E)O(V + E) time and uses O(V)O(V) space.