60ms concise python solution using topological sort

  • 5
    from collections import defaultdict
    #from set import Set
    class Solution:
        # @param {integer} numCourses
        # @param {integer[][]} prerequisites
        # @return {boolean}
        def canFinish(self, num_courses, prereq):
            if num_courses < 2:
                return True
            path = defaultdict(list)
            for c in prereq:
            searched = set()
            for start in path.keys():
                if not self.dfs(path, set(), start, searched):
                    return False
            return True
        def dfs(self, path, seen, curr, searched):
            if curr in searched:
                return True
            for x in path[curr]:
                if x in seen:
                    return False
                if not self.dfs(path, seen, x, searched):
                    return False
            return True

  • 0

    cannot believe python is so fast!

  • 0

    Thanks for sharing this fast and good solution. However, there's a small chance that the DFS exceeds the max. recursion depth. There is a test case containing 2,000 courses. If your program picks the root as the first course to run DFS, error will occur.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.