LeetCode LCR 106. 判断二分图

2026-03-28 HGNULB 约 10 分钟

文章信息 5 个分类 5 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 106. 判断二分图

题意分析

给一张用邻接表描述的无向图，graph[u] 列出所有与 u 相邻的点。问能否把全部节点分成两个集合，使得每一条边的两个端点分属不同集合。

把条件翻过来读更有用：题目其实是在问「有没有哪条边的两端被迫落在同一侧」。所以我们真正要维护的不是「谁在左边、谁在右边」这种绝对位置，而是节点之间的相对关系——u 与它的每个邻居必须异侧，而 u 的所有邻居彼此之间必须同侧（因为它们都在 u 的对面）。

「u 的所有邻居互相同侧」这句推论是整道题的题眼：它把「异侧」这种带方向的约束，转换成了「同侧」这种可以直接用集合合并来表达的无向约束。

约束里节点数 n ≤ 100，边数很小，说明任何 $O(n^2)$ 级别的做法都能过，重点不在效率而在建模是否正确。

图不保证连通，这一点必须留意：可能存在多个互相独立的分量，任何一个分量不满足条件整张图就不是二分图，所以必须遍历所有起点，不能只从 0 号点出发一次。

边界：没有边的图（所有 graph[u] 都是空）永远是二分图；自环会让一个点必须同时在两侧，直接判否（本题保证无自环）；一条边在邻接表里会出现两次（u 在 v 的列表里、v 也在 u 的列表里），重复处理同一条边不会影响结论。

解法：并查集维护连通性

核心思路

暴力做法是枚举每个节点归左还是归右，共 $2^n$ 种分配，逐一检查每条边。$n = 100$ 时不可想象。

瓶颈在于枚举了绝对位置，而题目只约束相对关系。把整个方案左右互换，合法性完全不变，所以 $2^n$ 里有一半是重复的；更关键的是，一旦确定了某个点的归属，与它相连的那一整片区域的归属就被连锁确定了，根本不需要逐点枚举。

抓住「相对关系」这个词，就能把问题化成集合合并：把必须同侧的节点合并进同一个集合。哪些点必须同侧？由前面的推论，对任意节点 u，它的邻居列表 graph[u] 里的所有点两两同侧。于是逐个 u 处理，把 graph[u] 里的点全部并到一起即可。

那什么时候判否？如果在处理某条边 (u, v) 时发现 u 和 v 已经处在同一个集合里，说明先前的约束已经逼着它们同侧，而这条边又要求它们异侧，矛盾出现，直接返回 false。

于是不变量可以写成：任何时刻，处于同一集合的节点在最终的划分中必须落在同一侧。算法从「每个点自成一集」开始（此时没有任何约束），每读一条边就往集合结构里追加一条「同侧」约束，同时检查这条边自身要求的「异侧」是否已被违反。

具体实现上有一个简洁的技巧：处理 u 的邻居列表时，不必两两配对合并，只要把每个邻居 v 都并到列表的第一个元素 graph[u][0] 上即可，同样能让整个列表归入一集，而且只需一次线性扫描。

全部边处理完仍未发现矛盾，说明这套「同侧」约束是自洽的，按集合染色即可得到合法的二分方案，返回 true。

解题步骤

初始化父数组 p，令 p[i] = i。为什么：起点是「没有任何约束」，每个节点单独成集；漏掉这一步会让所有点的父指针指向 0，等价于凭空断言全图同侧，任何有边的图都会被判否。

写带路径压缩的 find：if (p[x] != x) p[x] = find(p[x]); return p[x];。为什么要压缩：本题会对同一批节点反复查询代表元，压缩后树高几乎为 1，均摊近似 $O(1)$；即使不压缩本题也能过，但这是并查集的标准装备，白板上写它不会比不写长几个字符。

外层遍历每个节点 u，取出它的邻居列表 g = graph[u]。为什么要遍历所有 u 而不是只从 0 出发：图可能不连通，只搜一个分量会漏掉其余分量里的矛盾。

对列表中的每个 v，先判 find(u) == find(v)，成立则立刻返回 false。为什么必须先判后合：这条边要求 u 与 v 异侧，若二者已被判定同侧就是硬矛盾。顺序反了的话，下一步的合并会把它们真的并到一起，矛盾被自己抹平，永远检测不出来。

再执行 p[find(v)] = find(g[0])，把 v 并到列表首元素所在的集合。为什么并到 g[0]：g 里所有点都是 u 的邻居，彼此必须同侧，选任意一个当锚点都行，取首元素最省事；这样一趟扫描就完成了整个列表的合并。

所有节点处理完仍未返回 false，则返回 true。为什么可以直接下结论：此时全部「同侧」约束互相自洽，且没有任何一条边的两端落在同一集合，按集合任意二染色即为一组合法划分。

以 graph = [[1,3],[0,2],[1,3],[0,2]]（一个四元环 0-1-2-3-0）走一遍。初始 p = [0,1,2,3]，每点自成一集。

u = 0，g = [1,3]。处理 v = 1：find(0)=0、find(1)=1 不同，没有矛盾；合并 p[find(1)] = find(g[0]=1)，即 p[1] = 1，是一次空操作。处理 v = 3：find(0)=0、find(3)=3 不同；合并 p[find(3)] = find(1) = 1，于是 {1,3} 归为一集——这正体现了「0 的两个邻居必须同侧」。

u = 1，g = [0,2]。处理 v = 0：find(1)=1、find(0)=0 不同，合法；合并 p[find(0)] = find(g[0]=0) = 0，空操作。处理 v = 2：find(1)=1、find(2)=2 不同，合法；合并 p[find(2)] = find(0) = 0，于是 {0,2} 归为一集。

u = 2，g = [1,3]。find(2) 现在是 0，find(1)=1、find(3)=1，都与 0 不同，两条边都合法，合并操作全是空操作。

u = 3，g = [0,2]。find(3)=1，find(0)=0、find(2)=0，均不同，合法。

全部走完返回 true，对应的划分是 {0,2} 与 {1,3}，正是偶环的标准二分。

再看奇环 graph = [[1,2],[0,2],[0,1]]（三角形）。u = 0，g = [1,2]：处理 v = 1 合法，p[1] = find(1) = 1；处理 v = 2 合法，p[find(2)] = find(1) = 1，于是 {1,2} 同集。u = 1，g = [0,2]：处理 v = 0 合法；处理 v = 2 时 find(1) = 1、find(2) = 1 相等，矛盾出现，返回 false。三角形确实不是二分图，检测正好落在闭合那条边上。

代码实现

class Solution {
    private int[] p;

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        p = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
        for (int u = 0; u < n; ++u) {
            int[] g = graph[u];
            for (int v : g) {
                // 这条边要求 u、v 异侧，若二者已被判定同侧则矛盾。
                if (find(u) == find(v)) {
                    return false;
                }
                // u 的所有邻居必须彼此同侧，统一并到列表首元素上。
                p[find(v)] = find(g[0]);
            }
        }
        return true;
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

func isBipartite(graph [][]int) bool {
    n := len(graph)
    p := make([]int, n)
    for i := range p {
        p[i] = i
    }
    var find func(x int) int
    find = func(x int) int {
        if p[x] != x {
            p[x] = find(p[x])
        }
        return p[x]
    }
    for u, g := range graph {
        for _, v := range g {
            // 这条边要求 u、v 异侧，若二者已被判定同侧则矛盾。
            if find(u) == find(v) {
                return false
            }
            // u 的所有邻居必须彼此同侧，统一并到列表首元素上。
            p[find(v)] = find(g[0])
        }
    }
    return true
}

复杂度分析

时间复杂度：$O((n + m) \cdot \alpha(n))$，其中 $n$ 是节点数、$m$ 是边数（邻接表中每条边出现两次），$\alpha$ 是反阿克曼函数。凭什么：初始化扫一遍所有节点，主循环恰好把邻接表里的每一项处理一次，每一项做常数次 find，路径压缩后单次 find 的均摊代价接近常数。

空间复杂度：$O(n)$。凭什么：只额外维护长度为 $n$ 的父数组；find 的递归深度在路径压缩后趋于常数，最坏情况下也不超过 $n$。

关键点总结

判二分图的本质是「约束一致性」：边给出「异侧」约束，而「同一个点的所有邻居互相同侧」把它转成了可合并的「同侧」约束——这一步转换是并查集解法能成立的全部理由。

并查集只能表达「同类」，表达「异类」要靠两种手段：本题这种「把共同邻居并起来」，或者开二倍空间的「扩展域并查集」（i 与 i + n 分别代表两侧）。面试中能说出这两条路径，说明对并查集的适用边界有认识。

「先检查后合并」的顺序不可颠倒，这是所有用并查集做冲突检测的题目的通用铁律（684 冗余连接、990 等式方程同理）。

图不保证连通时必须对每个节点起跳，只跑一个分量是这类题的高频漏解点。

面试视角：更主流的答案其实是 BFS/DFS 二染色——给起点染 0，邻居染 1，遇到同色邻居即判否，时间同为线性且更直观。被问到时应当两种都能说，并指出染色法能顺带输出具体划分，而并查集只能回答可行性。

判否的时机就是「奇环闭合」的时刻，能把「不是二分图 ⟺ 存在奇环」这个等价命题说出来，是这道题最值钱的一句话。

易错点总结

忘记初始化 p[i] = i：graph = [[1],[0]] 时所有父指针默认是 0，find(0) 与 find(1) 都得 0，第一条边就被误判成矛盾，返回 false 而正确答案是 true。

先合并后检查：graph = [[1,2],[0,2],[0,1]]（三角形）中，若把 p[find(v)] = find(g[0]) 写在 if 之前，矛盾会被自己的合并抹平，返回 true 而正确答案是 false。

只从 0 号节点做一次遍历：graph = [[1],[0],[3,4],[2,4],[2,3]] 的第二个分量是三角形，只搜 0 所在分量会漏掉它，返回 true 而正确答案是 false。

合并时写成 p[v] = find(g[0]) 而不是 p[find(v)] = find(g[0])：直接改叶子的父指针会把 v 原先所在集合的其余成员甩掉，graph = [[1,2,3],[0],[0],[0]] 中 {1,2,3} 无法真正合成一集，后续矛盾检测失效。

find 里写成 return find(p[x]) 却不回写 p[x]：功能上仍正确但退化成无压缩版本，graph 退化成长链时递归层数逼近 $n$，链式数据下有栈溢出风险。

误以为邻接表里每条边只出现一次而跳过反向边：graph = [[1],[0]] 中若只处理 u < v 的方向，本题恰好仍能过，但同样的写法在需要统计度数或边数的题里会直接少一半。

把「同侧」和「异侧」的语义写反，即把 u 与 v 合并：graph = [[1],[0]] 会先合并 0 和 1，再遇到反向边 (1,0) 时检测出「矛盾」，返回 false 而正确答案是 true。

空邻居列表时访问 g[0]：本题的 g[0] 只在循环体内被访问，g 为空时循环不进入，天然安全；若把 find(g[0]) 提到循环外预先计算，graph = [[],[]] 会立刻越界。

认为「无环图一定是二分图，有环就不是」：graph = [[1,3],[0,2],[1,3],[0,2]] 是四元环却是二分图，只有奇环才会破坏二分性。

相似题目

题目	难度	考察点
785. 判断二分图	中等	与本题同题，可直接套用同一份代码
886. 可能的二分法	中等	给的是边列表而非邻接表，需要自己建图，且节点编号从 1 开始
990. 等式方程的可满足性	中等	同样是「同类合并 + 异类检测」，但必须先处理完所有等式再验不等式
684. 冗余连接	中等	用并查集检测环，返回造成环的那条边，是「先查后合」的另一个典型
547. 省份数量	中等	只统计连通分量个数，不涉及冲突检测，是并查集最基础的形态
765. 情侣牵手	困难	把情侣对当节点建图，答案是「节点数减连通分量数」，需要额外的贪心论证