• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Feb 24th, 2020 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution(object):
2.     def canFinish(self, numCourses, prerequisites):
3.         dead = [False] * numCourses
4.         visited = [False] * numCourses
5.         edges = [None] * numCourses
6.         backEdges = [None] * numCourses
7.         deg = [0] * numCourses
8.         for i in range(numCourses):
9.             edges[i] = list()
10.             backEdges[i] = list()
11.         for prereq in prerequisites:
12.             edges[prereq[0]].append(prereq[1])
13.             backEdges[prereq[1]].append(prereq[0])
14.             deg[prereq[0]] += 1
15.
16.         def cull(node):
17.             if deg[node] <= 0 and not dead[node]:
18.                 visited[node] = True
19.                 dead[node] = True
20.                 for par in backEdges[node]:
21.                     deg[par] -= 1
22.                     cull(par)
23.
24.         def dfs(node):
25.             cull(node)
27.                 return False
28.             visited[node] = True
29.             for child in edges[node]:
30.                 if not dead[child]:
31.                     if visited[child]:
32.                         return True
33.                     else:
34.                         if dfs(child):
35.                             return True
36.             return False
37.         for i in range(numCourses):
38.             if not visited[i]:
39.                 if dfs(i):
40.                     return False
41.         return True
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top