Workspace

Problem workspace

3 day streakD

Bipartite Graph Check

MediumGraphsConnectivity

The challenge

Decide whether an undirected graph can be split into two sets such that every edge connects vertices in different sets.

Equivalent to having no odd cycle. Check every component, not just the one containing A.

Example

A–B–C–F–A is an even cycle and admits two colors. Adding A–C creates triangle A–B–C, which cannot be two-colored.

Use the walkthrough below to inspect the input and each state change.

See Bipartite check, step by step

Follow the edges. Watch the state change.

Undirected · 6 vertices · 6 edgesA = 0, B = 1, …
Even cycle + tailUndirected graph with 6 vertices. Begin with all vertices uncolored. Bipartite graphs admit two colors with no equal-colored endpoints on any edge. Check every connected component. The edge list and state table below provide the graph in text.ABCDEF
CurrentVisited / acceptedUnvisitedLabels identify components or colors
Color (0 or 1)
ABCDEF
——————
Step 01 / 8

Begin with all vertices uncolored.

Bipartite graphs admit two colors with no equal-colored endpoints on any edge. Check every connected component.

color = [-1] * V
View input edges

A — B · A — F · B — C · C — F · C — D · D — E

Put it into code

BFS assigns each newly reached neighbor the opposite color.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

from collections import deque

def is_bipartite(adj):
    # Undirected adjacency list; include both directions.
    color = [-1] * len(adj)
    for root in range(len(adj)):
        if color[root] != -1:
            continue
        color[root] = 0
        queue = deque([root])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False
    return True

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap