207. Course Schedule

, , , ,

BFS (Kahn’s Algorithm)

reference: https://www.geeksforgeeks.org/dsa/topological-sorting-indegree-based-solution/

example to check cycle

1
2
3
1 -> 2 -> 3
    ^    |
    |____|

First, the indegree of each node is calculated:

  • Node 1 has an indegree of 0 (no incoming edges).
  • Node 2 has an indegree of 2 (one incoming edge from Node 1 and one from Node 3).
  • Node 3 has an indegree of 1 (one incoming edge from Node 2).

So we start with Node 1 in the queue (indegree 0).

  • dequeue Node 1, push it to result, and reduce the indegree of Node 2 by 1 (now indegree of Node 2 is 1).
  • Now, the queue is empty

However, Node 2 still has an indegree of 1, and Node 3 has an indegree of 1. This means there are still nodes with incoming edges that haven’t been processed, indicating a cycle in the graph.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adj = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses

        for p in prerequisites:
            adj[p[1]].append(p[0]) # to take p[0], need to finish p[1] first
            indeg[p[0]] += 1
        
        q = deque([c for c in range(numCourses) if indeg[c] == 0])
        topo = []
        while q:
            vtx = q.popleft()
            topo.append(vtx)

            for a in adj[vtx]:
                indeg[a] -= 1
                if indeg[a] == 0:
                    q.append(a)
        
        return len(topo) == numCourses

DFS

If uses only one array to track visited nodes, when encouters cases like

1
2
3
a  b
\ /
 c

When starts DFS from b after finishing DFS from a, c has been marked as visited. However, this “visited” is not from the current round of DFS, which is not a cycle actually. Therefore, we need two arrays to track visited nodes: one for all visited nodes, and one for nodes visited in the current round of DFS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adj = [[] for _ in range(numCourses)]

        for p in prerequisites:
            adj[p[1]].append(p[0])

        visited = [False] * numCourses
        cur_visited = [False] * numCourses

        def dfs(c)-> bool:
            visited[c] = True
            cur_visited[c] = True

            for a in adj[c]:
                if not visited[a]:
                    if not dfs(a):
                        return False
                elif cur_visited[a] == True:
                    return False

            cur_visited[c] = False
            return True

        for c in range(numCourses):
            if not visited[c]:
                if not dfs(c):
                    return False
        return True