0886. 可能的二分法【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - BFS 染色

1. 📝 题目描述

• leetcode

给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。

给定整数 n 和数组 dislikes，其中 dislikes[i] = [ai, bi]，表示不允许将编号为 ai 和 bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

---

示例 1：

输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]

示例 2：

输入：n = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false

示例 3：

输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false

---

提示：

• 1 <= n <= 2000
• 0 <= dislikes.length <= 10^4
• dislikes[i].length == 2
• 1 <= dislikes[i][j] <= n
• ai < bi
• dislikes 中每一组都 不同

2. 🎯 s.1 - BFS 染色

c

bool possibleBipartition(int n, int** dislikes, int dislikesSize, int* dislikesColSize) {
    int** graph = (int**)malloc(sizeof(int*) * (n + 1));
    int* gSize = (int*)calloc(n + 1, sizeof(int));
    int* gCap = (int*)malloc(sizeof(int) * (n + 1));
    for (int i = 0; i <= n; i++) { graph[i] = (int*)malloc(sizeof(int) * 4); gCap[i] = 4; }
    for (int i = 0; i < dislikesSize; i++) {
        int a = dislikes[i][0], b = dislikes[i][1];
        if (gSize[a] == gCap[a]) { gCap[a] *= 2; graph[a] = realloc(graph[a], sizeof(int) * gCap[a]); }
        graph[a][gSize[a]++] = b;
        if (gSize[b] == gCap[b]) { gCap[b] *= 2; graph[b] = realloc(graph[b], sizeof(int) * gCap[b]); }
        graph[b][gSize[b]++] = a;
    }
    int* color = (int*)calloc(n + 1, sizeof(int));
    int* queue = (int*)malloc(sizeof(int) * (n + 1));
    bool res = true;
    for (int i = 1; i <= n && res; i++) {
        if (color[i] != 0) continue;
        int front = 0, back = 0;
        queue[back++] = i; color[i] = 1;
        while (front < back && res) {
            int u = queue[front++];
            for (int j = 0; j < gSize[u]; j++) {
                int v = graph[u][j];
                if (color[v] == 0) { color[v] = -color[u]; queue[back++] = v; }
                else if (color[v] == color[u]) { res = false; break; }
            }
        }
    }
    for (int i = 0; i <= n; i++) free(graph[i]);
    free(graph); free(gSize); free(gCap); free(color); free(queue);
    return res;
}

js

/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function (n, dislikes) {
  const graph = Array.from({ length: n + 1 }, () => [])
  for (const [a, b] of dislikes) {
    graph[a].push(b)
    graph[b].push(a)
  }
  const color = new Array(n + 1).fill(0)
  for (let i = 1; i <= n; i++) {
    if (color[i] !== 0) continue
    const queue = [i]
    color[i] = 1
    while (queue.length) {
      const u = queue.shift()
      for (const v of graph[u]) {
        if (color[v] === 0) {
          color[v] = -color[u]
          queue.push(v)
        } else if (color[v] === color[u]) return false
      }
    }
  }
  return true
}

py

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        from collections import deque
        graph = [[] for _ in range(n + 1)]
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)
        color = [0] * (n + 1)
        for i in range(1, n + 1):
            if color[i] != 0: continue
            queue = deque([i])
            color[i] = 1
            while queue:
                u = queue.popleft()
                for v in graph[u]:
                    if color[v] == 0:
                        color[v] = -color[u]
                        queue.append(v)
                    elif color[v] == color[u]:
                        return False
        return True

• 时间复杂度：$O(V+E)$，其中 V 是人数，E 是双向边数
• 空间复杂度：$O(V+E)$

算法思路：

• 将不喜欢关系建成无向图，问题转化为判断图是否是二分图
• BFS 染色，相邻节点染不同色，若冲突则无法二分