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.

#785

Medium

auto_awesome图·DFS·traversal

LeetCode 题解工作台

判断二分图

存在一个无向图，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。…

深度优先搜索广度优先搜索并查集图

题目描述

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：

不存在自环（graph[u] 不包含 u）。
不存在平行边（graph[u] 不包含重复值）。
如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

如果图是二分图，返回 true ；否则，返回 false 。

示例 1：

输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
输出：false
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

示例 2：

输入：graph = [[1,3],[0,2],[1,3],[0,2]]
输出：true
解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。

提示：

graph.length == n
1 <= n <= 100
0 <= graph[u].length < n
0 <= graph[u][i] <= n - 1
graph[u] 不会包含 u
graph[u] 的所有值 互不相同
如果 graph[u] 包含 v，那么 graph[v] 也会包含 u

lightbulb

解题思路

方法一：染色法判定二分图

遍历所有节点进行染色，比如初始为白色，DFS 对节点相邻的点染上另外一种颜色。如果要染色某节点时，要染的目标颜色和该节点的已经染过的颜色不同，则说明不能构成二分图。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#765 情侣牵手 #685 冗余连接 II #684 冗余连接