美文网首页
剑指 Offer II 106. 二分图

剑指 Offer II 106. 二分图

作者: 邦_ | 来源:发表于2022-08-12 09:29 被阅读0次
    截屏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
                }
            }
            
        }
    
    
    
    
    

    相关文章

      网友评论

          本文标题:剑指 Offer II 106. 二分图

          本文链接:https://www.haomeiwen.com/subject/wtktgrtx.html