Is Graph Bipartite

+10

A graph has n nodes, labelled 0 to n-1. Each pair [a, b] in edges is an undirected edge between node a and node b. The graph may fall into several separate parts, and some nodes may have no edge at all.

A graph is bipartite when you can split its nodes into two groups so that every edge joins a node of one group to a node of the other. Return true if the graph is bipartite and false otherwise.

Function

isBipartite(n: integer, edges: integer-2d-array) → boolean

ninteger: the number of nodes, numbered 0 to n-1
edgesinteger-2d-array: the undirected edges, each a pair [a, b]
Returnsboolean: true if the nodes can be split into two groups with every edge between the groups, false otherwise

Constraints

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] with 0 ≤ a, b ≤ n-1 and a ≠ b
No edge appears twice, in either direction.

Examples

Input: n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Output: true
Explanation: Put nodes 0 and 2 in one group and nodes 1 and 3 in the other. Each of the four edges joins the two groups.

Input: n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
Output: false
Explanation: The edge [0, 1] splits fine and node 5 has no edges, but nodes 2, 3 and 4 form a triangle. One part that fails is enough to make the answer false.

Follow-up

When the graph is not bipartite, can you return one cycle of odd length as proof, listing its nodes in order?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Choosing a group for one node forces the rest of its connected part: a neighbour goes to the other group. Color each part with a breadth-first search that alternates two colors; the graph is bipartite exactly when no edge gets the same color at both ends. The graph can be disconnected, so every uncolored node starts a new search.

Try every split

Correct, but does not finish on the largest tests

Intuition

Try every split. Treat each node's group as one bit, so the n bits form a binary number, and counting from 0 to 2^n-1 visits every split once. For each split, check every edge, and return true if some split makes every edge cross. The splits double with each node: 20 nodes give about a million.

Algorithm

For each number from 0 to 2^n-1, put node i in the group given by bit i.
If every edge joins the two groups, return true.
If no split works, return false.

def isBipartite(n, edges):
    side = [0] * n  # side[x] is 0 or 1: the group of node x in the current split
    while True:
        # Does every edge cross between the two groups?
        if all(side[u] != side[v] for u, v in edges):
            return True
        # Move to the next split, counting in binary over side.
        i = 0
        while i < n and side[i] == 1:
            side[i] = 0
            i += 1
        if i == n:
            return False  # all 2^n splits have been tried
        side[i] = 1

Union-find on each node's neighbours

Intuition

Whatever group a node lands in, all its neighbours land in the other, so they share a group. For every node, merge all its neighbours into one union-find set; a set then holds nodes forced onto the same side. An edge with both ends in one set is forced to stay inside a group, so the graph is not bipartite.

The check catches every failure. Around an odd cycle, merging two edges at a time joins its first node with its last, and the closing edge joins those two. Without an odd cycle, every merge joins two nodes an even distance apart, which sit on the same side. A node's first neighbour, its anchor, names the set of its neighbours, so you merge as the edges stream past, with no adjacency lists. With union by size and path halving, the 2m merges and m checks cost O(m α(n)).

Algorithm

Set parent[x] = x and anchor[x] = -1 for every node.
For each edge [u, v], give each end the other as its anchor if it has none yet.
Merge v into the set of anchor[u], and u into the set of anchor[v].
Return false if some edge has both ends in one set, else true.

def isBipartite(n, edges):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n
    anchor = [-1] * n  # the first neighbour seen for each node

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    # All neighbours of a node must sit on one side: the side opposite the node.
    for u, v in edges:
        if anchor[u] == -1:
            anchor[u] = v
        if anchor[v] == -1:
            anchor[v] = u
        union(anchor[u], v)  # v joins the other neighbours of u
        union(anchor[v], u)  # u joins the other neighbours of v
    # An edge whose two ends were forced onto one side cannot cross.
    for u, v in edges:
        if find(u) == find(v):
            return False
    return True

Breadth-first two-coloring of every part

Intuition

A clash is final. The first color in a part is a free choice, and flipping it flips the whole part; every other color is forced by an edge. The search colors nodes by whether their distance from the start is even or odd, so two neighbours share a color only when the part has a cycle of odd length, and then no split exists.

A search sees only its own part, so go through all nodes and start a new search from each one still uncolored. In the third example the search from node 0 colors nodes 0 and 1. The search from node 2 gives node 2 color 0 and nodes 3 and 4 color 1, then finds [3, 4] with color 1 at both ends: false. Each node is colored and queued once, and each of the 2m list entries is compared once: O(n + m) time and space.

Algorithm

Build adjacency lists with each edge under both ends, and set every color to -1.
For each uncolored node in order, give it color 0 and put it in a queue.
Pop a node. Give each uncolored neighbour the opposite color and queue it; if a neighbour has the same color, return false.
Once every part is colored, return true.

from collections import deque


def isBipartite(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    color = [-1] * n  # -1: not colored yet, otherwise 0 or 1
    for start in range(n):
        if color[start] != -1:
            continue
        # A new component: its first node can take either color.
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in graph[node]:
                if color[nxt] == -1:
                    # A neighbour must take the other color.
                    color[nxt] = 1 - color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False  # this edge stays inside one group
    return True

Pitfalls and edge cases

Searching only from node 0. The third example is fine around node 0 and fails among nodes 2, 3 and 4.
Adding each edge to one list only. With edges [1, 0] and [2, 0], node 0 gets color 0 and sees no neighbours; node 1 then also gets color 0, and its edge to node 0 looks like a clash, although the path splits fine.
Coloring a node when you pop it. A node can then enter the queue twice, and the second visit overwrites the first. Color it when you push it.
Confusing bipartite with acyclic. The square has a cycle and is bipartite; only odd cycles break the split.

Frequently asked questions3

What is the time complexity of Is Graph Bipartite?

A breadth-first or depth-first coloring runs in O(n + m) for m edges: every node is colored once, and every edge is compared once from each end. The adjacency lists and colors take O(n + m) space. Union-find reaches the same answer in O(n + m α(n)).

Why does an odd cycle make a graph not bipartite?

Walk around the cycle and the groups must alternate: first, second, first, second. A cycle with an odd number of edges brings you back to the start after an odd number of switches, so the start would have to be in both groups. A graph is bipartite exactly when it has no cycle of odd length.

Should you use BFS or DFS to check whether a graph is bipartite?

Either works: the coloring rule is the same and only the visiting order changes. On large graphs write DFS with an explicit stack, since a recursive version can go one call deep per node.

def isBipartite(n, edges):
    # Write code here

Test #1

Test #2

Test #3

Arguments

n = 4
edges = [[0, 1], [1, 2], [2, 3], [3, 0]]

Expected Output

true

Is Graph Bipartite

Function

Constraints

Examples

Hints

Solution

Try every split

Union-find on each node's neighbours

Breadth-first two-coloring of every part

Pitfalls and edge cases

Frequently asked questions3

Similar problems