LeetCode LCR 106. 判断二分图

2026-03-28 HGNULB 约 5 分钟

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

分类

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

标签

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

题目描述

✅ LCR 106. 判断二分图

题意分析

给定无向图，判断能否把所有节点分为两组，使每条边的两个端点分属不同组。图可能不连通，必须检查全部分量。

对任意节点 u，所有邻居都必须位于它的另一侧，因此这些邻居彼此必须同侧。可以用并查集合并这种同侧关系，再检查它是否与边要求的异侧关系冲突。

解法：并查集合并同侧邻居

核心思路

[!blue]

并查集在这里保存同侧约束，不是原图的连通分量。两个节点属于同一集合，表示已有约束要求它们分在同侧；根不同则只表示尚未合并，不能直接认定它们必然异侧。

处理节点 u 的邻居列表 g 时，先检查每个邻居 v：若 find(u) == find(v)，先前约束要求它们同侧，而边 (u,v) 要求异侧，立即返回 false。否则把 v 与首个邻居 g[0] 合并，就能让 u 的所有邻居归入同一集合，不必两两合并。

每次合并都有共同邻居作为依据，所以合法二分图中的同一集合始终只含同侧节点，不会被误判。反过来，若图中存在奇环，取环上最后被外层循环处理的节点 u，再取它在环上的一个邻居 v。沿环另一侧从 u 到 v 的路程为偶数，其内部节点都已处理；这些节点不断把相隔两步的节点合并，就会使 u 与 v 已经同根。处理 u 时必然发现冲突。因此全部检查通过就排除了奇环，图可以分成两侧。

find 通过路径压缩让查询过的节点直接指向根，不改变已经确立的同侧关系。外层枚举每个节点，所以不会遗漏不连通分量。空邻接列表不会进入内层循环，也就不会访问不存在的 g[0]。

解题步骤

1. 初始化每个节点各自为根，暂时没有额外同侧约束。
2. 遍历所有节点 u 及其每个邻居 v，先检查两者是否已经同根。
3. 同根则返回 false；否则将 v 的根合并到首个邻居的根。
4. 所有节点处理完仍无冲突，返回 true。没有边的节点不施加任何约束。

代码实现

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
}

复杂度分析

设节点数为 V，无向边数为 E。

• 时间复杂度：$O((V+E)\log(V+1))$。每条无向边在邻接表中出现两次，每次只进行常数次并查集操作；当前代码只做路径压缩，使用其对数摊还上界。
• 空间复杂度：$O(V)$。父节点数组和查找过程的递归栈都在这一上界内。

这里没有按秩或按大小合并，不能直接套用两种优化同时存在时的反阿克曼界。路径压缩单独的分析见 MIT 课程讲义第 5 节。

关键点总结

[!green]

• 边的两端必须异侧，同一个节点的所有邻居必须同侧，这两类约束分别用检查和合并表达。
• 合并的是邻居之间的代表根，不能把节点 u 与它的邻居直接并为同侧。
• 奇环会通过一条偶数长度的替代路径，把相邻节点逼入同一个集合，最终触发冲突。
• 遍历全部节点即可覆盖所有分量，孤立节点自然不影响可行性。

易错点总结

[!yellow]

• 将原图边的两个端点直接合并，表达的会是同侧关系，与题目要求相反。
• 把所有不同根都理解为两两异侧，混淆了尚未确定关系与确定异侧。
• 只检查从节点零可达的部分，会遗漏其他分量中的奇环。
• 在遍历空邻接列表之前直接读取首项，会越界；当前代码只在存在邻居时使用首项。
• 合并时随意覆盖普通节点的父指针，而不连接两个根，可能破坏已建立的集合关系。

相似题目

题目	难度	关联与区别
886. 可能的二分法	中等	把不喜欢关系建成无向图后，能否分成两组就是同一个二分图染色判定。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/64382604

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！