Swift recursive DFS solution - Beats > 92% πŸ™πŸΌ


  • 0
    A
    func visitGraph(_ matrix: inout [[Int]], n: Int) {
            if matrix[n][n] == -1 { return }
            matrix[n][n] = -1 //mark visited
            
            let row = matrix[n]
            for i in 0..<row.count {
                if i != n && row[i] == 1 {
                    visitGraph(&matrix, n: i) // visit any unvisited neighbors
                }
            }
        }
        
        func findCircleNum(_ M: [[Int]]) -> Int {
            if M.count <= 1 { return M.count }
            
            var matrix = M
            var count = 0
            
            for j in 0..<matrix[0].count {
                if matrix[j][j] != -1 {
                    visitGraph(&matrix, n: j)
                    count += 1 // increment after every time a connected graph is visited
                }
            }
            
            return count
        }
    

    Solution is to use DFS to visit every node in a connectected graph. Number of connected graphs equals number of friend groups.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.