MediumDepth-First SearchBreadth-First SearchUnion FindGraph

Is Graph Bipartite?

1 approach, code in every language

You are given an undirected graph with n nodes labelled from 0 to n - 1, described by an adjacency list graph, where graph[u] is the list of nodes adjacent to node u. The graph has no self-edges and no repeated edges, and every edge is listed from both endpoints.

A graph is bipartite when its nodes can be split into two disjoint sets A and B so that every edge joins a node in A with a node in B (no edge stays inside a single set).

Return true if the graph is bipartite, and false otherwise.

Example 1

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output: false

Nodes 1 and 2 are neighbours and would have to sit in opposite sets, but they are also both neighbours of node 0, forcing an odd cycle. No valid two-way split exists.

Example 2

Input: graph = [[1,3],[0,2],[1,3],[0,2]]

Output: true

Placing nodes {0, 2} in one set and {1, 3} in the other makes every edge cross between the two sets.

Constraints

graph.length == n
1 <= n <= 100
0 <= graph[u].length < n
0 <= graph[u][i] <= n - 1
graph[u] does not contain u
All the values of graph[u] are unique
If graph[u] contains v, then graph[v] contains u

BFS / DFS 2-Coloring

Traverse each connected component, alternating colors between adjacent nodes; a same-color edge proves the graph is not bipartite.

Loading animation…

Intuition

A graph is bipartite exactly when it has no odd-length cycle. We can test this by coloring: pick a start node, color it, and give every neighbor the opposite color. Continuing this outward, each edge must connect two differently colored nodes. If we ever reach a node that already carries the same color as the node we came from, an odd cycle exists and the graph cannot be split in two. Because the graph may be disconnected, we launch a fresh traversal from every still-uncolored node.

Algorithm walkthrough

1Create a color array of length n filled with 0 (meaning uncolored); we will use +1 and -1 for the two sets.
2Loop over every node; skip any node that already has a color from a previous traversal.
3Color the start node +1 and push it into a queue to begin a BFS over its component.
4Pop a node, and for each neighbor: if uncolored, assign it the negated color of the current node and enqueue it.
5If a neighbor already shares the current node's color, return false immediately - an edge lies inside one set.
6If all components are colored without conflict, return true.

Implementation

from collections import deque
from typing import List

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [0] * n
        for start in range(n):
            if color[start] != 0:
                continue
            color[start] = 1
            queue = deque([start])
            while queue:
                node = queue.popleft()
                for neighbor in graph[node]:
                    if color[neighbor] == 0:
                        color[neighbor] = -color[node]
                        queue.append(neighbor)
                    elif color[neighbor] == color[node]:
                        return False
        return True

Time

O(V + E)

Space

O(V)

Every node and edge is visited once; the color array and queue use linear space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Two Shift Conflict Split is our own problem on the technique behind Is Graph Bipartite?: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free