class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
"""
main idea: BFS keep tracking of indegree, push into queue when in degree == 0
tc O(V+E) sc O(V+E)
"""
# (1)one node can direct to multiple node (2) there are isolated nodes (3) no circle
# can't use collections.defaultdict(list) since it ignores isolated nodes
children = [[] for i in range(numCourses)]
#some cases single nodes exist
ingree = [0]* numCourses
q = collections.deque()
# build graph, update indegree
for snd, fst in prerequisites:
children[fst].append(snd)
ingree[snd] += 1
# add vertices with 0 ingree into queue
for node in range(numCourses):
if ingree[node] == 0:
q.append(node)
cnt = numCourses
while q:
# remove edges connecting to cur
cur = q.popleft()
cnt -= 1
# put new nodes without in degree edges into queue
for child in children[cur]:
ingree[child] -= 1
if ingree[child] == 0:
q.append(child)
return cnt == 0
solution 2
class Solution:
"""
topological sort with DFS top to down: parent must be visited before child finish visited time O(N) space(N)
not visited: 0 ; visiting: -1; visited: 1
idea: if a node is always in state visiting (-1), there is a circle
@param: numCourses: a total n courses
@param: prerequisites: list of prerequisites pairs
@return true if being able to finish all course otherwise false
"""
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# graph, indegree record initialization
graph = [[] for i in range(numCourses)]
visited = [0] * numCourses
# build graph and indegree
for in_node, out_node in prerequisites:
graph[in_node].append(out_node)
# visite each node
for i in range(numCourses):
if self.dfs(graph,visited,i): #if there is a cycle, here i represent each course
return False
return True
#check if there is cycle, if yes return True, otherwise return False
def dfs(self, g, v, parent):
#if has visited, then skip
if v[parent] == 1:
return False
# if i th node is marked as being visited, then a cycle is found <=> dfs has a back edge
if v[parent] == -1:
return True
# substep1:--------------------- mark as being visited
v[parent] = -1
# visit all grandparents/ ascenster
for grandParent in g[parent]:
if self.dfs(g,v,grandParent):
return True
# substep2:--------------------- after visited all parents, mark as done visited
v[parent] = 1
return False