剑指 Offer II 106. 二分图

截屏2022-08-11 17.04.40.png

这道题主要是读懂题意= =。。
数组 graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
第0个节点 和1，2，3都有一条无向边
第1个节点 和0，2都有一条无向边
第2个节点 和0，1，3都有一条无向边
第3个节点 和0，2都有一条无向边

这个dfs比较绕

func isBipartite(_ graph: [[Int]]) -> Bool {
        let len = graph.count
        var colorArray = Array.init(repeating: 0, count: len)
        var isClose = false
        
        for node in 0..<len {
            if colorArray[node] == 0 {
                dfs(node,graph,1,&isClose,&colorArray)
            }
            //说明发现了相邻的颜色相同的。直接返回false
            if isClose {
                return false
            }
            
        }
        
    
        return true
    }
    
    func dfs(_ node:Int, _ graph: [[Int]],_ color:Int,_ isClose:inout Bool,_ colorArray: inout [Int]){

        if isClose {
            return
        }
        colorArray[node] = color
        let nextColor = color == 1 ? 2 : 1
        let arr = graph[node]
        for nextNode in arr {
            if colorArray[nextNode] == 0 {
                dfs(nextNode, graph, nextColor, &isClose, &colorArray)

            }
            else if colorArray[nextNode] == color {
                isClose = true
                return
            }
        }
        
    }