Solutions

# DFS checking if node is in current path to detect cycle; or topological sort using Kahn's algorithm. Both O(E + V) time and space. 
# graphs


# DFS cycle detection - O(E + V) time, O(E + V) space
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    preMap = {i:[] for i in range(numCourses)}
    for pr in prerequisites:
        preMap[pr[0]].append(pr[1])

    def dfs(course: int, path: set) -> bool:
        if course in path:
            return False

        path.add(course)
        for dep in preMap[course]:
            if not dfs(dep, path):
                return False

        path.remove(course) # backtrack
        preMap[course] = [] # only needed for performance
        return True


    for i in range(numCourses):
        if not dfs(i, set()):
            return False
    
    return True


# Topological sort (Kahn's algorithm) - O(E + V) time, O(E + V) space
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    # Build adjacency map and indegree array
    indegree = [0] * numCourses
    adjmap = {i: [] for i in range(numCourses)}
    for src, dst in prerequisites:
        indegree[dst] += 1     # in-degree of dst!
        adjmap[src].append(dst)

    # Add to the queue only courses with indegree == 0
    from collections import deque
    q = deque()
    for c in range(numCourses):
        if indegree[c] == 0:
            q.append(c)

    processed = 0
    while q:
        course = q.popleft()
        processed += 1
        
        for c in adjmap[course]:
            indegree[c] -= 1
            if indegree[c] == 0:
                q.append(c)

    return processed == numCourses