Course Schedule
- Difficulty: Medium
- Type: DFS/BFS
- link
Problem
Solution
- Use DFS to search for cylcic structure in graph
- Implement tree pruning by skipping the visited node
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = collections.defaultdict(list)
for course, prereq in prerequisites:
graph[course].append(prereq)
traced = set()
visited = set()
def dfs(i):
if i in traced:
return False
if i in visited:
return True
traced.add(i)
for y in graph[i]:
if not dfs(y):
return False
traced.remove(i)
visited.add(i)
return True
for x in list(graph):
if not dfs(x):
return False
return True