LeetCode #207: Course Schedule

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

To solve this problem, we can build an adjacency list from the given edge list. Then, we can use depth-first search (DFS) to traverse the graph, while keeping track of the state of each vertex. We use three different states for each vertex:

• state 0 : vertex is not visited. This is the default state.
• state -1 : vertex is being processed. Either all of its descendants are not processed or it’s still in the function call stack.
• state 1 : vertex and all its descendants are processed.

While traversing the graph using DFS, if we come across a vertex that is already being processed (state -1), it indicates the presence of a cycle, and we return False. If a vertex and all its descendants have been processed (state 1), then we can move to the next vertex. After traversing all vertices using DFS, if we don’t find a cycle, then it is possible to finish all courses, and we return True.

Steps:

1. Define a function to build an adjacency list from the given edge list.
2. Define a function to perform DFS while keeping track of the state of each vertex.
3. Traverse each vertex using DFS, if we find a cycle, stop and return False. Otherwise, return True.

class Solution:
    def buildAdjacencyList(self, n, edgesList):
            adjList = [[] for _ in range(n)]
            # c2 (course 2) is a prerequisite of c1 (course 1)
            # i.e c2c1 is a directed edge in the graph
            for c1, c2 in edgesList:
                adjList[c2].append(c1)
            return adjList
        
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # build Adjacency list from Edges list
        adjList = self.buildAdjacencyList(numCourses, prerequisites)

        state = [0] * numCourses

        def hasCycle(v):
            if state[v] == 1:
                return False
            if state[v] == -1:
                return True
            state[v] = -1
            for i in adjList[v]:
                if hasCycle(i):
                    return True

            state[v] = 1
            return False
        for v in range(numCourses):
            if hasCycle(v):
                return False

        return True

Time Complexity: The time complexity of this solution is O(V+E), where V is the number of vertices, and E is the number of edges in the graph.

Space Complexity: The space complexity of this solution is O(V+E), where V is the number of vertices, and E is the number of edges in the graph.