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.

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

python

▶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

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.

06

Complexity

Time

O(V + E)

Space

O(V)

Each node colored once, each edge checked twice.