题目:
给定一个无向图 graph,当这个图为二分图时返回 true。
如果我们能将一个图的节点集合分割成两个独立的子集 A 和 B,并使图中的每一条边的两个节点一个来自 A 集合,一个来自 B 集合,我们就将这个图称为二分图。
graph 将会以邻接表方式给出,graph[i]表示图中与节点 i 相连的所有节点。每个节点都是一个在 0 到 graph.length-1 之间的整数。这图中没有自环和平行边:graph[i] 中不存在 i,并且 graph[i]中没有重复的值。
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释:
无向图如下:
0----1
| |
| |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释:
无向图如下:
0----1
| \ |
| \ |
3----2
我们不能将节点分割成两个独立的子集。
位置 | 节点 | A | B |
---|---|---|---|
0 | [1,3] | [0] | [1,3] |
1 | [0,2] | [0,0] | [1,3] |
2 | [1,3] | [0,0,2] | [1,3,1,1,3] |
3 | [0,2] | [0,0,0,2] | [1,3,1,1,3] |
结果 | - | [0,2] | [1,3] |
逻辑
换种思路:
注意
实现
/**
* @param {number[][]} graph
* @return {boolean}
*/
var isBipartite = function (graph) {
let _result = false,
dp = new Map(),
A = new Map(),
B = new Map()
for (let i = 0; i < graph.length; i++) {
// 跳过已经存存放的节点,如不跳过已存放节点,那默认填充A会与已填充元素冲突
if (!dp.has(i)) {
pushItem(i, 'A')
}
}
function pushItem(i, flag) {
// 已经存存放的节点确认是否冲突
if (dp.has(i)) {
_result = _result || flag !== dp.get(i)
return
}
// 存入A组
if (flag === 'A') {
A.set(i)
dp.set(i, 'A')
} else {
// 存入B组
B.set(i)
dp.set(i, 'B')
}
// graph[i]的所有元素都不能与i在同一个分组
for (let j = 0; j < graph[i].length; j++) {
pushItem(graph[i][j], flag === 'A' ? 'B' : 'A')
}
}
return !_result
}
优化
上面最终生成了 A,B 两个组,但是这两个组其实并没有参与判断,则优化删除 A,B 两个组对象
/**
* @param {number[][]} graph
* @return {boolean}
*/
var isBipartite = function (graph) {
let _result = false,
dp = new Map()
for (let i = 0; i < graph.length; i++) {
// 跳过已经存存放的节点,如不跳过已存放节点,那默认填充A会与已填充元素冲突
if (!dp.has(i)) {
pushItem(i, 'A')
}
}
function pushItem(i, flag) {
// 已经存存放的节点确认是否冲突
if (dp.has(i)) {
_result = _result || flag !== dp.get(i)
return
}
dp.set(i, flag)
// graph[i]的所有元素都不能与i在同一个分组
for (let j = 0; j < graph[i].length; j++) {
pushItem(graph[i][j], flag === 'A' ? 'B' : 'A')
}
}
return !_result
}
/**
* @param {number[][]} graph
* @return {boolean}
*/
var isBipartite = function (graph) {
let dp = new Map()
for (let i = 0; i < graph.length; i++) {
if (dp.has(i)) continue
let queue = [i]
dp.set(i, 1)
while (queue.length) {
let j = queue.shift()
let A = dp.get(j),
B = -A
for (let k = 0; k < graph[j].length; k++) {
let item = graph[j][k]
if (!dp.has(item)) {
dp.set(item, B)
queue.push(item)
} else if (dp.get(item) != B) {
return false
}
}
}
}
return true
}