Leetcode 207. Course Schedule

📅2023-07-14🧐109

let's take a look on the graphs:

Actually, all we need to do is find the loops in the graphs. If we find a loop, which means we can not finish the course.

To detect loops in a graph, we could use DFS or BFS with backtrack.

from collections import defaultdict

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        def dfs(node):
            nonlocal has_cycle
            if onPath[node]:
                has_cycle = True

            if node in seen:
                return False

            seen.add(node)
            onPath[node] = True
            for nei in graph[node]:
                dfs(nei)
            onPath[node] = False

        has_cycle = False
        onPath = [False] * numCourses
        seen = set()

        graph = defaultdict(list)
        for v, u in prerequisites:
            graph[u].append(v)

        for i in range(numCourses):
            dfs(i)

        return not has_cycle

Use has_cycle to track the result.

Then use onPath = [False] * numCourses to see is a vertex on our current path or not, if it is, that means we have a cycle

The seen = set() is to save the vertex we have visited

Then use defaultdict to build our graph from the input

In the function dfs :

onPath[node] = True # this vertex is on our path, mark as True in the preorder
for nei in graph[node]:
    dfs(nei)
onPath[node] = False # when we finish current search, we backtrack the status in the postorder.

Since the graph maybe not connected like this input:

[[1,0],[1,2],[4,3]]

So we need to use a loop start search on every node.

Then we just return do we found a cycle.