⚡Flashcard Drill➔
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

  1. Two-colour the graph: assign a colour to a start node and the opposite colour to each neighbour.
  2. If a neighbour already has the same colour as the current node, the graph is not bipartite.
  3. The graph may be disconnected, so every uncoloured node must start a new colouring.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems