Course Schedule

Intuition

• Can run DFS, but make a dependency list first.
• By making a dependency list, you can thereafter use DFS and check that there are no cycles when you start from each respective node.
• If there are, then there is a cycle (including self cycle)
• This algorithm also works on the idea of transitive dependencies, i.e. if A depends on B and B depends on C, then A must depend on C.
• Consequently, if A depends on C, then C cannot depend on any A or B as there would be a cycle in the graph.
• In this case we are also using the idea of Reductions by reducing the concept of
• A cycle in this case means there is a transitive dependency
• Alternatively, you could use Kahns Topological Sort

Complexity

Runtime

• Adjacency list makes runtime go down from $O(V\times E)$ to $O(V+E)$ for the adjacency list creation
• TLE would give $O((V+E)\times V)$, where V is the number of nodes in the graph and E is the connections.
  • That is because you must run DFS for each node on all the nodes it is connected to (which could be all of them).
• To speed up, we use a DP dictionary to store the previous computation:
  • If a node reaches another node which had previously been computed fully, then the node that reached it must also contain the same result.
• Alternatively to save space, we could just clear that dependency list such that the algorithm immediately returns true due to having no prerequisites and immediately returning true.
• Topological Sort takes $O(V+E)$ to generate the adjacency list as well as

Space

• $O(V+E)$ to hold the dependency list, which contains all the nodes and edges connected directly to those nodes.
• An additional $O(V)$ space if using the DP dictionary.

Code

Topological Sort

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegree = [0] * numCourses
        dependency = defaultdict(list)
 
        for u, v in prerequisites:
            dependency[u].append(v)
            indegree[v] += 1
 
        q = deque()
        for i, degree in enumerate(indegree):
            if degree == 0:
                q.append(i)
 
        while q:
            u = q.popleft()
            if u in dependency:
                for v in dependency[u]:
                    indegree[v] -= 1
                    if indegree[v] == 0:
                        q.append(v)
 
        return sum(indegree) == 0

Dependency Clearing

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        dependency = defaultdict(list)
        for u, v in prerequisites:
            dependency[u].append(v)
        
        seen = set()
        valid = {}
        def dfs(u):
            if u in seen:
                return False
            if u not in dependency:
                return True
 
            seen.add(u)
            for v in dependency[u]:
                if dfs(v) == False:
                    valid[u] = False
                    return False
            seen.remove(u)
            dependency[u] = []
            return True
 
        for u in dependency.keys():
            if dfs(u) == False:
                return False
        return True

DP Dictionary

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        dependency = defaultdict(list)
        for u, v in prerequisites:
            dependency[u].append(v)
        
        seen = set()
        valid = {}
        def dfs(u):
            if u in seen:
                valid[u] = False
            if u not in dependency:
                valid[u] = True
            if u in valid:
                return valid[u]
                
            seen.add(u)
            for v in dependency[u]:
                if dfs(v) == False:
                    valid[u] = False
                    return False
            seen.remove(u)
            
            valid[u] = True
            return True
 
        for u in dependency.keys():
            if dfs(u) == False:
                return False
        return True

TLE

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        dependency = defaultdict(list)
        for u, v in prerequisites:
            dependency[u].append(v)
        
        seen = set()
        def dfs(u):
            if u in seen:
                return False
            if u not in dependency:
                return True
 
            seen.add(u)
            for v in dependency[u]:
                if dfs(v) == False:
                    return False
            seen.remove(u)
            return True
 
        for u in dependency.keys():
            if dfs(u) == False:
                return False
        return True

Notes

---

References

https://leetcode.com/problems/course-schedule