LeetCode #785 Medium

Is Graph Bipartite?

Can the nodes be split into two sets so every edge crosses between the sets? (2-colorability.)

graphbfsdfscoloring

02

Intuition

Bipartite means 2-colorable: paint a node red, all its neighbors blue, their neighbors red, and so on. If the paint spreads without ever forcing a node to take both colors, the two colors are the two sets. A conflict happens exactly when the graph has an odd cycle — the color parity comes back wrong.

How to spot this pattern

Two-colouring is a traversal with one extra rule: every neighbour must get the opposite colour, and a neighbour that already holds your colour proves an odd cycle. Bipartite is exactly "no odd cycle", so this single check settles it. Either BFS or DFS works — only the container changes.

03

Approach

1

Color while traversing

color[] starts uncolored. For each uncolored node (graph may be disconnected), start a BFS or DFS: color the start 0, and give every neighbor the opposite color of its parent.

2

Detect the contradiction

When traversal meets an already-colored neighbor, it must have the opposite color. Same color = odd cycle = not bipartite, return false immediately.

3

BFS vs DFS

Identical logic either way — this covers both the BFS and DFS variants of the sheet. Only the visit order differs; the coloring rule and conflict test are the same.

04

Solution & live demo

▶1class Solution:
▶2    def isBipartite(self, graph):
▶3        n = len(graph)
▶4        color = [-1] * n
▶5        for s in range(n):                 # every component
▶6            if color[s] != -1: continue
▶7            color[s] = 0
▶8            queue = [s]
▶9            for u in queue:                # BFS; a stack gives DFS
▶10                for v in graph[u]:
▶11                    if color[v] == -1:
▶12                        color[v] = 1 - color[u]
▶13                        queue.append(v)
▶14                    elif color[v] == color[u]:
▶15                        return False
▶16        return True

05

Common pitfalls

Checking only the component containing vertex 0

✗ Wrong

color[0] = 0
queue = [0]

✓ Right

for s in range(n):
    if color[s] != -1: continue
    color[s] = 0

The graph may be disconnected, and a conflict can live entirely inside a component unreachable from 0. Every uncoloured vertex needs to seed its own search.

Using a boolean visited array instead of colours

✗ Wrong

if seen[v]: continue
seen[v] = True

✓ Right

if color[v] == -1:
    color[v] = 1 - color[u]
elif color[v] == color[u]:
    return False

Visited-ness alone can't detect the conflict — you need to know which side a vertex is on. Three states are required: uncoloured, side 0, side 1.

Rejecting any neighbour that is already coloured

✗ Wrong

elif color[v] != -1: return False

✓ Right

elif color[v] == color[u]: return False

A neighbour coloured the opposite side is exactly what a bipartite graph should look like — that's a valid edge, not a conflict. Only a same-colour neighbour breaks it.

06

Edge cases

Disconnected graph

Outer loop restarts coloring in every uncolored component.

Isolated node / no edges

Trivially bipartite.

Self-loop

A node adjacent to itself needs both colors — immediately false.

07

Complexity

Time

O(V + E)

Space

O(V)

Each node colored once, each edge checked twice.