There are a total of
numCourses courses you have to take, labeled from
numCourses - 1. You are given an array prerequisites where
prerequisites[i] = [ai, bi] indicates that you must take course
bi first if you want to take course
For example, the pair
[0, 1], indicates that to take course
0 you have to first take course
true if you can finish all courses. Otherwise, return
Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
from collections import defaultdict class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: adj = defaultdict(set) seen = set() for a, b in prerequisites: adj[b].add(a) def cycle_found(adj, u, seen): if u in seen: return True seen.add(u) for v in adj[u]: if cycle_found(adj, v, seen): return True adj[u] =  seen.remove(u) return False for i in range(numCourses): if cycle_fount(adj, i, seen): return False return True