Problem Statement

Is Graph Bipartite

You are given an undirected graph. A graph is a set of dots, called nodes, with lines, called edges, connecting some of them. "Undirected" means each line works both ways, so if A connects to B, then B connects to A. The question: can you split all the nodes into exactly two groups so that every edge goes between the two groups, never inside one group? If yes, the graph is "bipartite" (bi means two, partite means parts). A simple way to check is to paint the graph with two colors. Walk the graph and give each node a color, always painting a node's neighbor the opposite color. If you ever need to paint a node a color it already disagrees with, the two-group split is impossible, so the graph is not bipartite. The graph is given as a list where graph[i] holds the neighbors of node i.

mediumGraphBFSGraphsTime: O(V+E) · Space: O(V)

Signals to notice

can graph be 2-coloredno adjacent nodes same colorodd cycle detection

Brute force first

Try all 2^n colorings — exponential. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

BFS/DFS coloring: assign color 0 to start, color 1 to neighbors, color 0 to their neighbors, etc. If any neighbor already has the same color, not bipartite. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `graph=[[1,2,3],[0,2],[0,1,3],[0,2]]`

color=[-1,-1,-1,-1]; i=0 uncolored → color[0]=0, queue=[0]
pop 0; neighbors 1,2,3 all -1 → color[1]=1,color[2]=1,color[3]=1, queue=[1,2,3]
pop 1; nei 0: color[0]=0 ≠ color[1]=1, ok
pop 1 cont; nei 2: color[2]=1 == color[1]=1 → conflict (odd cycle)
return False

What must stay true

A graph is bipartite if and only if it contains no odd-length cycles. BFS coloring detects this — a conflict means an odd cycle exists. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

color = array of -1 sized V
for each vertex i:
  if color[i] set: skip
  color[i]=0; queue=[i]
  while queue: node=pop; for nei in adj[node]:
    if uncolored: color[nei]=1-color[node]; push nei
    elif color[nei]==color[node]: return False
return True

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Only checking one connected component — the graph may be disconnected. Run the coloring from every unvisited vertex. The fix is usually to return to the meaning of each move, not just the steps themselves.

Graphs Pattern