LeetCode 886. 可能的二分法

约 5 分钟
文章信息 9 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节 拼多多 快手
标签
深度优先搜索 广度优先搜索 图 并查集

题目描述

✅ 886. 可能的二分法

image-20260928225303905

image-20260928225303906

题意分析

把编号 1 到 n 的所有人分到两组，使每一对给定的互斥关系两端都不在同组，判断能否做到。两组人数不要求相等，没有直接关系的两个人可以同组，也可以不同组。

每对关系都是不能同组的共同约束，可以表示成无向图的一条边。问题就是能否用两种颜色标记所有节点，让每条边连接不同颜色；图可能有多个互不相连的部分和孤立节点。

解法：二分图判定

核心思路

[!blue]

用 color 保存组别，零表示尚未决定，正一和负一表示两组。对一个还没处理过的连通块，先给起点任意一种颜色；一旦起点颜色确定，所有沿边相邻的节点都被强制取相反颜色。

用队列逐个传播约束。遇到未着色邻居，就给它 -color[cur]，并立即入队；颜色同时充当已访问标记，避免一个节点从多个方向被重复加入。遇到已着色邻居时，不需要重染，只检查它是否与当前节点异色。

如果某条边两端已经同色，就产生无法满足的约束。之前的颜色都是沿起点到各节点的路径强制得出的，要改变其中一个节点，就必须连带改变整条路径的颜色；把整个连通块统一换色，冲突边仍是同色。因此不需要换起点颜色再试一次，可以直接判定无解。这种矛盾对应无法用两色交替绕完的奇数环。

一个连通块通过检查，只说明其中所有边都满足约束，不能代表其他部分也合法。外层必须遍历所有编号，从每个未着色节点开始一轮搜索；互不相连的部分可以独立选择起点颜色，不会互相影响。所有边检查完都无冲突，就得到了完整合法分组。

解题步骤

  1. 为每个关系的两个端点互相添加邻接边，建立无向图。
  2. 初始化颜色数组为零，按编号扫描所有人，已着色的跳过。
  3. 为新连通块的起点赋色并入队，依次取出节点检查所有邻居。
  4. 未着色邻居赋相反色并入队；已着色邻居与当前同色时立即返回 false。
  5. 全部连通块均无冲突，返回 true。

代码实现

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[] graph = new List[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] d : dislikes) {
            graph[d[0]].add(d[1]);
            graph[d[1]].add(d[0]);
        }

        int[] color = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            // 逐个启动未着色连通块，不能只检查第一块
            if (color[i] != 0) {
                continue;
            }

            Deque<Integer> queue = new ArrayDeque<>();

            queue.offer(i);
            color[i] = 1;

            while (!queue.isEmpty()) {
                int cur = queue.poll();

                for (int next : graph[cur]) {
                    if (color[next] == 0) {
                        // 沿关系强制异色，颜色同时充当访问标记
                        color[next] = -color[cur];
                        queue.offer(next);
                    } else if (color[next] == color[cur]) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}

func possibleBipartition(n int, dislikes [][]int) bool {
    graph := make([][]int, n+1)
    for _, d := range dislikes {
        graph[d[0]] = append(graph[d[0]], d[1])
        graph[d[1]] = append(graph[d[1]], d[0])
    }

    color := make([]int, n+1)
    for i := 1; i <= n; i++ {
        // 逐个启动未着色连通块，不能只检查第一块
        if color[i] != 0 {
            continue
        }
        queue := make([]int, 0)
        queue = append(queue, i)
        color[i] = 1

        for len(queue) > 0 {
            cur := queue[0]
            queue = queue[1:]
            for _, next := range graph[cur] {
                if color[next] == 0 {
                    // 沿关系强制异色，颜色同时充当访问标记
                    color[next] = -color[cur]
                    queue = append(queue, next)
                } else if color[next] == color[cur] {
                    return false
                }
            }
        }
    }

    return true
}

复杂度分析

  • 时间复杂度：$O(n + E)$，E 为互斥关系数，每个节点入队一次，每条无向边从两端各检查一次。
  • 空间复杂度：$O(n + E)$，用于邻接表、颜色数组与搜索队列。

关键点总结

[!green]

  • 关系只要求相邻节点异色，不要求组人数相同或同组节点彼此相连。
  • 起点任意赋色后，同一连通块里的颜色关系都由边强制决定。
  • 同色冲突不会因整块换色而消失，可以立即判定失败。
  • 逐个启动未着色连通块，才能覆盖全部约束。

易错点总结

[!yellow]

  • 只搜索第一个连通块，会漏掉其他分量里的矛盾环。
  • 只添加单向邻接关系，不能完整表达两端不得同组的无向约束。
  • 用零同时表示一种组别和未访问状态，会混淆传播与访问判断。
  • 已着色邻居出现同色时只是跳过，会把已经冲突的分组继续当成有效结果。
  • 每次遇到邻居就重染，可能覆盖之前的强制约束，掩盖不可能同时满足的关系。

相似题目

题目 难度 关联与区别
785. 判断二分图 中等 先把不喜欢关系转为无向图，再直接复用二分图染色判定。
1042. 不邻接植花 中等 同样图染色，但原题可用四种颜色且度数受限，本题只有两组，奇环会导致无解。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/24649919
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！