【2022-10-16每日一题】886. 可能的二分法[Medium]
2022-10-16
3分钟阅读时长
2022-10-16每日一题：886. 可能的二分法
难度：Medium
标签：深度优先搜索 、 广度优先搜索 、 并查集 、 图
给定一组 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 <= 20000 <= dislikes.length <= 104dislikes[i].length == 21 <= dislikes[i][j] <= nai < bidislikes中每一组都 不同
方法一：染色法+深度优先搜索
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func possibleBipartition(n int, dislikes [][]int) bool {
g := make([][]int, n)
for _, d := range dislikes {
x, y := d[0]-1, d[1]-1 // 1~n 转换为 0~n-1
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
color := make([]int, n) // color[x] = 0 表示未访问节点 x， 1 红色，2蓝色
var dfs func(x, c int) bool
dfs = func(x, c int) bool {
color[x] = c
for _, y := range g[x] {
// 颜色相同 或者 染色失败 返回 false
// 3^c: 如果c=1结果为2， 如果c=2结果为1
if color[x] == color[y] || color[y] == 0 && !dfs(y, 3^c) {
return false
}
}
return true
}
for i, c := range color {
// 染色
if c == 0 && !dfs(i, 1) {
return false
}
}
return true
}
复杂度分析
- 时间复杂度：O(n + m)，其中 n 题目给定的人数，m 为给定的 dislike 数组的大小。
- 空间复杂度：O(n + m)，其中 n 题目给定的人数，m 为给定的 dislike 数组的大小。
方法二：染色法+广度优先搜索
func possibleBipartition(n int, dislikes [][]int) bool {
g := make([][]int, n)
for _, d := range dislikes {
x, y := d[0]-1, d[1]-1
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
// color[x] = 0 标识未染色 1红色，-1蓝色
color := make([]int, n)
for i, c := range color {
// 未染色
if c == 0 {
color[i] = 1
q := []int{i}
for len(q) > 0 {
x := q[0]
q = q[1:]
// 取出对立面进行染色
for _, y := range g[x] {
if color[x] == color[y] {
return false
}
if color[y] == 0 {
color[y] = -color[x]
q = append(q, y)
}
}
}
}
}
return true
}
复杂度分析
- 时间复杂度：O(n + m)，其中 n 题目给定的人数，m 为给定的 dislike 数组的大小。
- 空间复杂度：O(n + m)，其中 n 题目给定的人数，m 为给定的 dislike 数组的大小。
方法三：并查集
// 并查集实现模板
type UnionFind struct {
parent, rank []int
}
func newUnionFind(n int) UnionFind {
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
return UnionFind{parent, make([]int, n)}
}
func (uf UnionFind) find(x int) int {
if uf.parent[x] != x {
// 路径压缩
uf.parent[x] = uf.find(uf.parent[x])
}
return uf.parent[x]
}
func (uf UnionFind) union(x, y int) {
x, y = uf.find(x), uf.find(y)
if x == y {
return
}
// 路径压缩优化
if uf.rank[x] > uf.rank[y] {
uf.parent[y] = x
} else if uf.rank[x] < uf.rank[y] {
uf.parent[x] = y
} else {
uf.parent[y] = x
uf.rank[x]++
}
}
func (uf UnionFind) isConnectted(x, y int) bool {
return uf.find(x) == uf.find(y)
}
func possibleBipartition(n int, dislikes [][]int) bool {
g := make([][]int, n)
for _, d := range dislikes {
x, y := d[0]-1, d[1]-1
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
uf := newUnionFind(n)
for x, nodes := range g {
for _, y := range nodes {
uf.union(nodes[0], y) // 相当于染色
if uf.isConnectted(x, y) {
return false
}
}
}
return true
}
复杂度分析
- 时间复杂度：O(n + mα(n))，其中 n 题目给定的人数，m 为给定的 dislike 数组的大小，α 是反 Ackerman 函数。
- 空间复杂度：O(n + m)，其中 n 题目给定的人数，m 为给定的 dislike 数组的大小。