Sign in
Skip to solution
mediumDSA

How do you check if a graph is bipartite?

987 views
01

Understand the problem

Explain 2-coloring.

graphsbfscoloring
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Try to 2-color the graph with BFS/DFS: assign a node one color and its neighbors the opposite. If you ever need to give two adjacent nodes the same color, it isn't bipartite (it has an odd cycle). O(V+E).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

BFS 2-coloring
Run Playground
from collections import deque

def is_bipartite(graph):
    n = len(graph)
    color = [0] * n            # 0 = uncolored, 1 / -1 the two colors
    for start in range(n):
        if color[start] != 0:
            continue
        color[start] = 1
        q = deque([start])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == 0:
                    color[v] = -color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False
    return True


# --- demo ---  adjacency lists
print(is_bipartite([[1, 3], [0, 2], [1, 3], [0, 2]]))   # True   (square / even cycle)
print(is_bipartite([[1, 2], [0, 2], [0, 1]]))           # False  (triangle / odd cycle)
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 38 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track