NeetCode #595LC-785MediumGraphs
← Back to All Problems#595 · #785 · Is Graph Bipartite?(判断二分图)
📌 Problem Statement & Constraints
There is an undirected graph with
n nodes where graph[i] lists the neighbours of node i. Return whether the graph is bipartite: the nodes can be split into two sets with every edge crossing between them. Constraints: 1 <= n <= 100, 0 <= graph[i].length < n, no self-loops or parallel edges.💡 Core Algorithmic Approaches
- Two-colour the graph: assign a colour to a start node and the opposite colour to each neighbour.
- If a neighbour already has the same colour as the current node, the graph is not bipartite.
- The graph may be disconnected, so every uncoloured node must start a new colouring.
- BFS or DFS both work; the colouring is the invariant.
💻 Benchmark Python3 Implementation
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
n = len(graph)
color = [0] * n # 0 = uncoloured, 1 / -1 = the two colours
for start in range(n):
if color[start]:
continue
color[start] = 1
stack = [start]
while stack:
node = stack.pop()
for nxt in graph[node]:
if color[nxt] == 0:
color[nxt] = -color[node] # opposite colour
stack.append(nxt)
elif color[nxt] == color[node]:
return False # same colour on an edge -> not bipartite
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V + E): each node and edge is visited once.
💾 Space Complexity
O(V) for the colour array.
⚠️ Interview Pitfalls & Follow-ups
- Starting the colouring from only node 0: a disconnected graph needs every component coloured.
- Using
!=instead of==in the conflict check: the conflict is when a neighbour shares the current colour. - Treating 0 as a valid colour: 0 is reserved for "uncoloured", hence the ±1 scheme.
- Confusing bipartite with acyclic: a 4-cycle is bipartite but has a cycle.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.