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, …
CurrentVisited / acceptedUnvisitedLabels identify components or colors
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| — | — | — | — | — | — |
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] * VView 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#include <queue>
#include <vector>
bool is_bipartite(const std::vector<std::vector<int>>& adj) {
int n = static_cast<int>(adj.size());
std::vector<int> color(n, -1);
for (int root = 0; root < n; ++root) {
if (color[root] != -1) continue;
std::queue<int> queue;
queue.push(root);
color[root] = 0;
while (!queue.empty()) {
int u = queue.front();
queue.pop();
for (int v : adj[u]) {
if (color[v] == -1) {
color[v] = 1 - color[u];
queue.push(v);
} else if (color[v] == color[u]) return false;
}
}
}
return true;
}