785. 判断二分图

[AmelloAster]

785. 判断二分图

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。

解题代码

var isBipartite = function (graph) {
    let black = []
    let red = []
    let result = true
    // 0 -未染色 1 黑色 2 红色

    const test = (dir, i) => {
        graph[i].forEach(r => {
            if (dir === 'black ' && black.includes(r)) {
                result = false
            }
            if (dir === 'red ' && red.includes(r)) {
                result = false
            }
        })
        if (result) {
            if (dir === 'black ') {
                red.push(...graph[i])
            }
            if (dir === 'red ') {
                black.push(...graph[i])
            }
        }
    }

    for (let i = 0; i < graph.length; i++) {
        if (result) {
            if (!black.length && !red.length) {
            if (graph[i].length) {
                black.push(i)
                red.push(...graph[i])
                graph[i].forEach(r => {
                    black.push(...graph[r])
                })
            }
        }

        if (!black.includes(i) && !red.includes(i)) {
            if (graph[i].length) {
                if (graph[i].some(r => black.includes(r))) {
                    red.push(i)
                    black.push(...graph[i])
                }
                if (graph[i].some(r => red.includes(r))) {
                    black.push(i)
                    red.push(...graph[i])
                }

                if (
                    !graph[i].some(r => black.includes(r)) &&
                    !graph[i].some(r => red.includes(r))
                ) {
                    black.push(i)
                    red.push(...graph[i])
                }
            }
        }

        if (black.includes(i)) {
            test('black', i)
        }

        if (red.includes(i)) {
            test('red', i)
        }
        }
        else {
            return result
        }
    }

    return result
}

解题思路

1. 取一个顶点染色，假如顶点染红色 那顶点相连的 点则染黑色，而顶点相连的点的相连点则染红色
2. 判断当前顶点是否已经染色，如果没有 则判断此顶点相连的点是否已染色来反推顶点的颜色 如果相连的点也都未染色 则直接重复第一步
3. 如果当前顶点已经染色 如果当前顶点是红色 那么此顶点相连的点应为黑色 假如相连的点中颜色冲突 则结束

解题效率

执行结果：
通过
显示详情
执行用时：
108 ms, 在所有 JavaScript 提交中击败了13.79%的用户
内存消耗：
39.7 MB, 在所有 JavaScript 提交中击败了100.00%的用户