mediumDSA

How do you check if a graph is bipartite?

Q: How do you check if a graph is bipartite?

**Intuition.** A graph is bipartite if you can split its vertices into two groups so that **every edge crosses between groups** — equivalently, you can **2-color** it with no two adjacent nodes sharing a color. Traverse with BFS/DFS, coloring each neighbor the opposite color; a conflict means an **odd cycle**, so it's not bipartite. 2-color via BFS: neighbor gets opposite color 0 <circle cx="220" cy="50" r="18" fill="#f59e0b" fill-opacity="0.2" s

987 views

Understand the problem

Explain 2-coloring.

graphsbfscoloring

Attempt it yourself

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

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

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)

Join the discussion

Discussion (0)

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

How do you check if a binary tree is balanced?

How do you remove the nth node from the end of a linked list?