Solutions

# Topological sort (Kahn's algorithm) or DFS. Direction of edges changes depending on algorithm.
# graphs


# Topological sort (Kahn's algorithm) - O(V+E) time, O(V+E) space
def findOrder1(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    # NB: we need prereq -> [courses] for Kahn's (for DFS we need course -> [prereqs])
    adj = {i: [] for i in range(numCourses)} # {i: [courses i is a prereq of]}
    indregree = [0] * numCourses
    for a,b in prerequisites:
        adj[b].append(a) # a is prereq of b
        indregree[a] += 1

    from collections import deque
    q = deque()

    for c in range(numCourses):
        if indregree[c] == 0:
            q.append(c)

    out = []
    while q:
        c = q.popleft()
        out.append(c)

        for nei in adj[c]:
            indregree[nei] -= 1
            if indregree[nei] == 0:
                q.append(nei)
    
    if any(i > 0 for i in indregree):
        return []
    else:
        return out


# DFS - O(V+E) time, O(V+E) space
def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    prereq = {i: [] for i in range(numCourses)} 
    # NB: in DFS we need course -> prereqs, whereas in Kahn's we need prereq -> courses.
    for crs, pre in prerequisites:
        prereq[crs].append(pre)  # pre is a prereq of crs

    out = []

    def dfs(c: int, cycle: set[int], visited: set[int]) -> bool:
        if c in cycle:
            return False
        if c in visited:
            return True
        
        cycle.add(c)
        for pre in prereq[c]:
            if not dfs(pre, cycle, visit):
                return False
        cycle.remove(c)
        visit.add(c)
        out.append(c)
        return True

    # NB: we need both a cycle set and a visited set,
    # because we want to be able to detect cycles even if we've already visited some nodes.
    visit = set()
    # NB: iterate over all courses, not just the ones in prereq,
    # because there may be courses with no prereqs that we still need to add to the output.
    for crs in range(numCourses):
        if not dfs(crs, set(), visit):
            return []
    return out
    
# Topological sort (DFS) - O(V+E) time, O(V+E) space
def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    # NB: we need prereq -> [courses] for Kahn's (for DFS we need course -> [prereqs])
    adj = {i: [] for i in range(numCourses)}
    indegree = [0] * numCourses
    for nxt, pre in prerequisites:
        indegree[nxt] += 1
        adj[pre].append(nxt) # all courses that have pre as a prereq

    output = []

    def dfs(node: int):
        output.append(node)
        indegree[node] -= 1
        for nei in adj[node]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                dfs(nei)

    for i in range(numCourses):
        if indegree[i] == 0:
            dfs(i)

    return output if len(output) == numCourses else []