深度优先搜索，广度优先搜索和并查集，3 解法求解《886. 可能的二分法》
2022-10-16 07:44:38
深度优先搜索，广度优先搜索和并查集，3 解法求解《886. 可能的二分法》
例题
886. 可能的二分法
给定一组 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 中每一组都 不同
答案
深度优先搜索
var possibleBipartition = function(n, dislikes) {
const visited = new Uint8Array(n + 1), grah = Array.from({length: n + 1}, _ => [])
const d = i => {
for (const child of grah[i]) {
if (visited[child] === 0) {
visited[child] = visited[i] ^ 3
if (d(child) === false) return false
} else if (visited[child] !== (visited[i] ^ 3)) return false
}
return true
}
for (const [x, y] of dislikes) {
grah[x].push(y)
grah[y].push(x)
}
for (let i = 1; i <= n; i++) {
if (visited[i] > 0) continue
if (visited[i] === 0) visited[i] = 1
if (d(i) === false) return false
}
return true
};function possibleBipartition(n: number, dislikes: number[][]): boolean {
const visited = new Uint8Array(n + 1), grah = Array.from({length: n + 1}, _ => [])
const d = (i: number): boolean => {
for (const child of grah[i]) {
if (visited[child] === 0) {
visited[child] = visited[i] ^ 3
if (d(child) === false) return false
} else if (visited[child] !== (visited[i] ^ 3)) return false
}
return true
}
for (const [x, y] of dislikes) {
grah[x].push(y)
grah[y].push(x)
}
for (let i = 1; i <= n; i++) {
if (visited[i] > 0) continue
if (visited[i] === 0) visited[i] = 1
if (d(i) === false) return false
}
return true
};广度优先搜索
var possibleBipartition = function(n, dislikes) {
const visited = new Uint8Array(n + 1), grah = Array.from({length: n + 1}, _ => [])
const bfs = i => {
const q = [i]
while (q.length) {
const n = q.shift()
for (const child of grah[n]) {
if (visited[child] === 0) {
visited[child] = visited[n] ^ 3
q.push(child)
} else if (visited[child] !== (visited[n] ^ 3)) return false
}
}
return true
}
for (const [x, y] of dislikes) {
grah[x].push(y)
grah[y].push(x)
}
for (let i = 1; i <= n; i++) {
if (visited[i] > 0) continue
if (visited[i] === 0) visited[i] = 1
if (bfs(i) === false) return false
}
return true
};function possibleBipartition(n: number, dislikes: number[][]): boolean {
const visited = new Uint8Array(n + 1), grah = Array.from({length: n + 1}, _ => [])
const bfs = (i: number): boolean => {
const q = [i]
while (q.length) {
const n = q.shift()
for (const child of grah[n]) {
if (visited[child] === 0) {
visited[child] = visited[n] ^ 3
q.push(child)
} else if (visited[child] !== (visited[n] ^ 3)) return false
}
}
return true
}
for (const [x, y] of dislikes) {
grah[x].push(y)
grah[y].push(x)
}
for (let i = 1; i <= n; i++) {
if (visited[i] > 0) continue
if (visited[i] === 0) visited[i] = 1
if (bfs(i) === false) return false
}
return true
};并查集
var possibleBipartition = function(n, dislikes) {
const grah = Array.from({length: n + 1}, _ => []), u = new UnionFind(n + 1)
for (const [x, y] of dislikes) {
grah[x].push(y)
grah[y].push(x)
}
for (let i = 1; i <= n; i++) {
const m = grah[i].length
for (let j = 1; j < m; j++) {
u.union(grah[i][0], grah[i][j])
if (u.isConnected(i, grah[i][j])) return false
}
}
return true
};
class UnionFind {
constructor (n) {
this.parents = new Uint16Array(n)
this.sizes = new Uint16Array(n).fill(1)
while (n--) this.parents[n] = n
}
union(x, y) {
const rootX = this.find(x), rootY = this.find(y)
if (rootX === rootY) return
if (this.sizes[rootX] >= this.sizes[rootY]) this.parents[rootY] = rootX
else this.parents[rootX] = rootY
}
find (x) {
while (x !== this.parents[x]) x = this.parents[this.parents[x]]
return x
}
isConnected(x, y) {
return this.find(x) === this.find(y)
}
}function possibleBipartition(n: number, dislikes: number[][]): boolean {
const grah = Array.from({length: n + 1}, _ => []), u = new UnionFind(n + 1)
for (const [x, y] of dislikes) {
grah[x].push(y)
grah[y].push(x)
}
for (let i = 1; i <= n; i++) {
const m = grah[i].length
for (let j = 1; j < m; j++) {
u.union(grah[i][0], grah[i][j])
if (u.isConnected(i, grah[i][j])) return false
}
}
return true
};
class UnionFind {
parents: number[]
sizes: number[]
constructor (n) {
this.parents = new Array(n)
this.sizes = new Array(n).fill(1)
while (n--) this.parents[n] = n
}
union(x, y) {
const rootX = this.find(x), rootY = this.find(y)
if (rootX === rootY) return
if (this.sizes[rootX] >= this.sizes[rootY]) this.parents[rootY] = rootX
else this.parents[rootX] = rootY
}
find (x) {
while (x !== this.parents[x]) x = this.parents[this.parents[x]]
return x
}
isConnected(x, y) {
return this.find(x) === this.find(y)
}
}