Check if the directed graph has cycle. An edge 
[0, 1] means 1 has to be done before 0. So, we add edge 
DFS
Check if graph has back edge.
Time and space complexity is that of DFS: 
class Solution:
def build_graph(self, n, edges) -> Dict[int, Set[int]]:
adj_list = {u: set() for u in range(n)}
for u, v in edges:
adj_list[v].add(u)
return adj_list
def explore_cycle(self, u, adj_list, visited, onstack) -> bool:
visited[u] = True
onstack[u] = True
for v in adj_list[u]:
if visited[v] and onstack[v]:
# Found back edge
return True
if visited[v]:
continue
if self.explore_cycle(v, adj_list, visited, onstack):
return True
onstack[u] = False
return False
def has_cycle(self, adj_list) -> bool:
n = len(adj_list)
visited, onstack = [False]*n, [False]*n
for u in adj_list:
if visited[u]:
continue
if self.explore_cycle(u, adj_list, visited, onstack):
return True
return False
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
n, edges = numCourses, prerequisites
adj_list = self.build_graph( n, edges )
return not self.has_cycle( adj_list )
In-degree
Check if all courses can be topologically sorted.
class Solution:
def build_graph(self, n, edges) -> Dict[int, Set[int]]:
adj_list = {u: set() for u in range(n)}
for u, v in edges:
adj_list[v].add(u)
return adj_list
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
n, edges = numCourses, prerequisites
adj_list = self.build_graph( n, edges )
ind = { u: 0 for u in range(n) }
for v, u in edges:
ind[v] += 1
curr_sources = [u for u, d in ind.items() if d == 0]
topo_order = []
while curr_sources:
topo_order.extend( curr_sources )
new_sources = []
for u in curr_sources:
for v in adj_list[u]:
ind[v] -= 1
if ind[v] == 0:
new_sources.append(v)
curr_sources = new_sources
return len(topo_order) == numCourses
unreasonably effective 
Leave a comment