Skip to content

785. Is Graph Bipartite?

On LeetCode ->

Problem

Determine whether every connected component of an undirected graph can be split into two groups so that each edge joins opposite groups.

Input:  graph = [[1,3],[0,2],[1,3],[0,2]]
State:  groups = {0,2} | {1,3}
Output: true

Key trick

Color each node with one of two colors using DFS or BFS. Every uncolored neighbor gets the opposite color; an edge whose endpoints have the same color proves the graph is not bipartite.

Trap

  • Starting traversal only from node 0 misses conflicts in disconnected components.
  • Non-adjacent nodes do not necessarily belong to the same partition.
  • Marking nodes as merely visited is insufficient; their assigned color must be stored.
  • A graph is not bipartite exactly when it contains an odd-length cycle.

Why is it interesting?

It turns a global partitioning requirement into a local graph-coloring rule that can be checked in one traversal.

Python solution

class Solution:
    def isBipartite(self, graph: list[list[int]]) -> bool:
        n = len(graph)
        colors = [0] * n

        for start in range(n):
            if colors[start] != 0:
                continue

            colors[start] = 1
            stack = [start]

            while stack:
                node = stack.pop()

                for nei in graph[node]:
                    if colors[nei] == 0:
                        colors[nei] = -colors[node]
                        stack.append(nei)
                    elif colors[nei] == colors[node]:
                        return False

        return True
  • Time: \(O(V + E)\)
  • Space: \(O(V)\)

Comment on my solution

  • The observation that adjacent nodes must be in different partitions is correct.
  • The claim that non-adjacent nodes must be in the same partition is false; their relationship may be unconstrained.
  • n is undefined and should be derived from len(graph).
  • graph[A] is invalid because A is a set, not a node index.
  • Checking not A and not B initializes only once and does not handle disconnected components.
  • Explicit color assignments are simpler than maintaining two sets and make conflicts easy to detect.
# Ideas:
# - if a and b not adjacent, they must be in the same partition
# - 2 adjacents nodes can't be in the same partition
# - Iterate on nodes trying to build A and B following these rules
#   - stop early when one can't be satified

# WRONG
class Solution:
    def isBipartite(self, graph: list[list[int]]) -> bool:
        A = set()
        B = set()
        for node in range(n):
            if not A and not B:
                A.add(node)
                for adj in graph[A]:
                    B.add(adj)
        # DON'T KNOW HOW TO SOLVE IT