785. Is Graph Bipartite?

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split its set of nodes into two independent subsets A and B, such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn't contain any element twice.

Example 1:

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: We cannot find a way to divide the set of nodes into two independent subsets.

Constraints:

• 1 <= graph.length <= 100
• 0 <= graph[i].length < 100
• 0 <= graph[i][j] <= graph.length - 1
• graph[i][j] != i
• All the values of graph[i] are unique.
• The graph is guaranteed to be undirected.

# @lc code=start
using LeetCode

function is_bipartite(graph::Vector{Vector{Int}})
    for edge in graph
        edge .+= 1
    end
    color = fill(0, length(graph))
    q = Queue{Int}()
    for i in 1:length(graph)
        if color[i] != 0
            continue
        end
        color[i] = 1
        enqueue!(q, i)
        while !isempty(q)
            root = dequeue!(q)
            for neighbor in graph[root]
                if color[neighbor] == 0
                    color[neighbor] = -color[root]
                    enqueue!(q, neighbor)
                elseif color[neighbor] == color[root]
                    return false
                end
            end
        end
    end
    return true
end
# @lc code=end

is_bipartite (generic function with 1 method)

This page was generated using DemoCards.jl and Literate.jl.