leetCodeGraph.swift

// ------------------MEDIUM------------------ //
// https://leetcode.com/problems/clone-graph/
// DFS
// Time: O(n), Space: O(n)
func cloneGraph(_ node: Node?) -> Node? {
    var dict = [Int : Node]()

    return cloneNode(node, &dict)
}

func cloneNode(_ node: Node?, _ dict: inout [Int : Node]) -> Node? {
    guard let node = node else { return nil }

    if let node = dict[node.val] { return node } 

    var newNode = Node(node.val)
    dict[node.val] = newNode

    for neighbor in node.neighbors {
        if let newNeighbor = cloneNode(neighbor, &dict) {
            newNode.neighbors.append(newNeighbor)
        }
    }

    return newNode
}


// https://leetcode.com/problems/course-schedule/
// O(V+E), O(V+E)
// BFS + topo sort
func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
    var preqToCourses = [Int : [Int]]() // V+E
    var inDegrees = Array(repeating: 0, count: numCourses) // V
    var queue = [Int]() // V

    // E
    for pair in prerequisites {
        let course = pair[0]
        let preq = pair[1]

        preqToCourses[preq, default: []].append(course)
        inDegrees[course] = inDegrees[course] + 1
    }
    // V
    for i in 0..<inDegrees.count {
        if inDegrees[i] == 0 { queue.append(i) }
    }

    var index = 0
    // V + E
    while index < queue.count {
        let preq = queue[index]
        index += 1
        guard let courses = preqToCourses[preq] else { continue }

        for course in courses {
            let newInDegree = inDegrees[course] - 1
            if newInDegree == 0 {
                queue.append(course)
            } else {
                inDegrees[course] = newInDegree
            }
        }
    }
    return index == numCourses
}

// DFS
// Time: O(V+E), O(V+E)
func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
    var preqToCourses = [Int : [Int]]()
    var status = Array(repeating: 0, count: numCourses)

    for pair in prerequisites {
        let course = pair[0]
        let preq = pair[1]
        preqToCourses[preq, default: []].append(course)        
    }

    // V + E
    for vertex in 0..<status.count {
        if hasCycle(vertex, &status, preqToCourses) { return false }
    }

    return true
}

// status: 0 = unvisited, 1 = visited, 2 = processed
func hasCycle(_ vertex: Int, _ status: inout [Int], _ preqToCourses: [Int : [Int]]) -> Bool {
    if status[vertex] == 2 { return false } 
    if status[vertex] == 1 { return true } 

    if let courses = preqToCourses[vertex] {
        status[vertex] = 1
        for course in courses {
            if hasCycle(course, &status, preqToCourses) { return true }
        }
    }

    status[vertex] = 2
    return false
}