LeetCode 210: Course Schedule II

We build a directed graph where vertex set is the courses and an edge $(u \rightarrow v)$ represents $u \ \text{is-prerequisite-of} \ v$ . So, input [0, 1] would be added as the edge $( 1 \rightarrow 0 )$ .

If the graph does not have a cycle, it is a DAG and we emit the courses in topological order.

DFS

Presence of back edge signals cycle in the graph and decreasing post order is the topological order.

Time and space: $\mathcal{O}( \text{numCourses} + |\text{prerequisites}| )$ .

class Solution:
    def build_graph(self, n, edges) -> Dict[int, Set[int]]:
        adj_list = {u : set() for u in range(n)}
        for v, u in edges:
            adj_list[u].add(v)
        return adj_list
    
    def explore(self, u, adj_list, visited, onstack, post) -> bool:
        visited.add(u)
        onstack.add(u)

        for v in adj_list[u]:
            # back edge
            if (v in visited) and (v in onstack):
                return True
            if v in visited:
                continue
            if self.explore(v, adj_list, visited, onstack, post):
                return True

        post.append(u)
        onstack.remove(u)
        
        return False
    
    def dfs(self, adj_list) -> Tuple[bool, List[int]]:
        visited, onstack = set(), set()
        post = []
        for u in adj_list:
            if u in visited:
                continue
            if self.explore(u, adj_list, visited, onstack, post):
                return True, []
        return False, post[::-1]

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        n, edges = numCourses, prerequisites
        adj_list = self.build_graph( n, edges )
        has_cycle, topo_order = self.dfs( adj_list )
        if has_cycle:
            return []
        return topo_order

In-degree

If the graph has a cycle, some vertices will never become sources. In that case, some vertices will be missing from the topo_order. Otherwise, vertices added in the order as they become sources would be a topological order.

class Solution:
    def build_graph(self, n, edges) -> Dict[int, Set[int]]:
        adj_list = {u : set() for u in range(n)}
        for v, u in edges:
            adj_list[u].add(v)
        return adj_list

    def build_indegree_map(self, adj_list) -> Dict[int, int]:
        inmap = {u : 0 for u in adj_list}
        for u, edges in adj_list.items():
            for v in edges:
                inmap[v] += 1
        return inmap

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        n, edges = numCourses, prerequisites
        adj_list = self.build_graph( n, edges )
        inmap = self.build_indegree_map( adj_list )

        topo_order = []
        curr_sources = [u for u, d in inmap.items() if d == 0]
        while curr_sources:
            topo_order.extend( curr_sources )
            new_sources = []
            for u in curr_sources:
                for v in adj_list[u]:
                    inmap[v] -= 1
                    if inmap[v] == 0:
                        new_sources.append(v)
            curr_sources = new_sources

        return topo_order if len(topo_order) == n else []

unreasonably effective