802. Find Eventual Safe States

leetcode802.swift

class Solution {
    func eventualSafeNodes(_ graph: [[Int]]) -> [Int] {
        
        var record = [Int:Bool]()
        
        func visit(_ i:Int, _ visited:inout Set<Int>) -> Bool {
            if let isSafe = record[i] {
                return isSafe
            }
            
            if visited.contains(i) {
                record[i] = false
                return false
            }
            
            visited.insert(i)
            
            for neighbor in graph[i] {
                if !visit(neighbor, &visited) {
                    record[i] = false
                    visited.remove(i)
                    return false
                }
            }
            
            visited.remove(i)
            record[i] = true
            return true
        }
        
        var result = [Int]()
        
        for (index, node) in graph.enumerated() {
            var visited = Set<Int>()
            if visit(index, &visited) {
                result.append(index)
            }
        }
        
        return result
    }
}