#785

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Is Graph Bipartite?

Determine whether an undirected graph can be split into two independent sets using DFS, BFS, or Union Find patterns.

depth first search breadth first search union find graph

Problem Statement

You are given an undirected graph with n nodes labeled from 0 to n - 1. The graph is represented as a 2D array graph where graph[u] contains all nodes adjacent to node u. Each edge is bidirectional and appears in both nodes' adjacency lists. Your task is to determine whether this graph can be partitioned into two sets where no two nodes in the same set are connected.

A graph is bipartite if its nodes can be divided into two independent sets A and B such that every edge connects a node from set A to a node from set B. Return true if such a partition exists and false otherwise. Consider the constraints that the graph length is between 1 and 100, edges are unique, and no node contains itself as a neighbor.

Examples

Example 1

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output: false

There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2

Input: graph = [[1,3],[0,2],[1,3],[0,2]]

Output: true

We can partition the nodes into two sets: {0, 2} and {1, 3}.

Constraints

graph.length == n
1 <= n <= 100
0 <= graph[u].length < n
0 <= graph[u][i] <= n - 1
graph[u] does not contain u.
All the values of graph[u] are unique.
If graph[u] contains v, then graph[v] contains u.

Solution Approach

Depth-First Search Coloring

Perform a DFS traversal and assign alternating colors to nodes. If a neighbor has the same color during traversal, return false immediately. Continue recursively until all connected components are verified.

Breadth-First Search Leveling

Use BFS to traverse each component, assigning levels as pseudo-colors. Nodes at the same level represent one set, and adjacent levels represent the other. Detect conflicts if a neighbor is on the same level.

Union Find for Set Separation

Use a Union Find structure to group nodes into two sets. For each edge, union nodes into separate groups. If two connected nodes end up in the same group, the graph is not bipartite.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(V + E) for DFS or BFS traversal, as each node and edge is visited once. Union Find adds near O(1) operations per edge, so overall complexity remains O(V + E). Space complexity is O(V) for coloring or parent arrays, and O(V + E) for adjacency representation.

What Interviewers Usually Probe

Ask to explain why DFS or BFS coloring ensures bipartiteness.
Probe for handling disconnected components in the graph.
Check understanding of how Union Find can represent two disjoint sets for bipartite checking.

Common Pitfalls or Variants

Common pitfalls

Failing to initialize all nodes before DFS/BFS leading to missed components.
Overlooking that an edge might connect two nodes already in the same set, causing incorrect true result.
Confusing directed and undirected graph behavior when checking adjacency relationships.

Follow-up variants

Check bipartiteness in a weighted undirected graph while ignoring weights.
Determine if a graph with additional constraints like forbidden node pairs is bipartite.
Extend bipartite check to k-partite graph verification for multiple independent sets.

FAQ

What is the main pattern used in the Is Graph Bipartite? problem?

The primary pattern is graph traversal with DFS or BFS combined with coloring to detect conflicts between connected nodes.

Can Union Find efficiently check bipartiteness for disconnected graphs?

Yes, Union Find can manage multiple components by grouping nodes and checking for conflicts within each disjoint set.

How do I handle graphs with isolated nodes?

Isolated nodes do not affect bipartiteness and can be colored arbitrarily without causing conflicts.

Why might DFS fail if implemented incorrectly for bipartite checking?

DFS may miss a component or incorrectly assign colors if the recursion does not cover all nodes, leading to false positives.

What is the difference between BFS leveling and DFS coloring in this problem?

BFS uses levels to assign pseudo-colors iteratively, while DFS assigns colors recursively; both detect conflicts but traversal order differs.

terminal

Solution

Solution 1: Coloring Method to Determine Bipartite Graph

Traverse all nodes for coloring. For example, initially color them white, and use DFS to color the adjacent nodes with another color. If the target color to be colored is different from the color that the node has already been colored, it means that it cannot form a bipartite graph.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        def dfs(a: int, c: int) -> bool:
            color[a] = c
            for b in graph[a]:
                if color[b] == c or (color[b] == 0 and not dfs(b, -c)):
                    return False
            return True

        n = len(graph)
        color = [0] * n
        for i in range(n):
            if color[i] == 0 and not dfs(i, 1):
                return False
        return True

Solution 2: Union-Find

For this problem, if it is a bipartite graph, then all adjacent nodes of each vertex in the graph should belong to the same set and not be in the same set as the vertex. Therefore, we can use the union-find method. Traverse each vertex in the graph, and if it is found that the current vertex and its corresponding adjacent nodes are in the same set, it means that it is not a bipartite graph. Otherwise, merge the adjacent nodes of the current node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        def dfs(a: int, c: int) -> bool:
            color[a] = c
            for b in graph[a]:
                if color[b] == c or (color[b] == 0 and not dfs(b, -c)):
                    return False
            return True

        n = len(graph)
        color = [0] * n
        for i in range(n):
            if color[i] == 0 and not dfs(i, 1):
                return False
        return True

Continue Practicing

#765 couples holding hands #685 redundant connection ii #684 redundant connection