class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        dead = [False] * numCourses
        visited = [False] * numCourses
        edges = [None] * numCourses
        backEdges = [None] * numCourses
        deg = [0] * numCourses
        for i in range(numCourses):
            edges[i] = list()
            backEdges[i] = list()
        for prereq in prerequisites:
            edges[prereq[0]].append(prereq[1])
            backEdges[prereq[1]].append(prereq[0])
            deg[prereq[0]] += 1

        def cull(node):
            if deg[node] <= 0 and not dead[node]:
                visited[node] = True
                dead[node] = True
                for par in backEdges[node]:
                    deg[par] -= 1
                    cull(par)

        def dfs(node):
            cull(node)
            if dead[node]:
                return False
            visited[node] = True
            for child in edges[node]:
                if not dead[child]:
                    if visited[child]:
                        return True
                    else:
                        if dfs(child):
                            return True
            return False
        for i in range(numCourses):
            if not visited[i]:
                if dfs(i):
                    return False
        return True