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)
  26.             if dead[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. OK, I Understand
Top