中等

问题描述

给定一组 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 <= 104
• dislikes[i].length == 2
• 1 <= dislikes[i][j] <= n
• ai < bi
• dislikes 中每一组都 不同

染色法

首先使用 $dislikes$ 进行建图，同时建立一个与人数相等的数组 $colors$ ，默认值为 $-1$，用于记录各个人所在的组的颜色，随后从 $1$ 到 $n$ 遍历每一个人，若当前的人未划分颜色，则将其划分为颜色 $0$ ，然后对图进行深度优先搜索，将其对立的人划分为颜色 $1$，若此过程中出现冲突情况，则说明无法划分，返回 $false$，若最终能够完成划分，则返回 $true$。

/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function (n, dislikes) {
  const graph = new Array(n + 1).fill(0).map(() => [])
  const colors = new Array(n + 1).fill(-1)
  const dfs = (num, color) => {
    colors[num] = color
    for (const other of graph[num]) {
      if (colors[other] === -1) {
        if (!dfs(other, 1 ^ color)) {
          return false
        }
      } else if (colors[other] === color) {
        return false
      }
    }
    return true
  }
  for (const [a, b] of dislikes) {
    graph[a].push(b)
    graph[b].push(a)
  }
  for (let i = 1; i <= n; i++) {
    if (colors[i] === -1) {
      if (!dfs(i, 0)) return false
    }
  }
  return true
}

• 时间复杂度：$O(n + m)$，其中 $n$ 题目给定的人数，$m$ 为给定的 $dislike$ 数组的大小。
• 空间复杂度：$O(n + m)$，其中 $n$ 题目给定的人数，$m$ 为给定的 $dislike$ 数组的大小。