60ms concise python solution using topological sort


  • 5
    Y
    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:
                path[c[0]].append(c[1])
    
            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
    
                seen.add(x)
                if not self.dfs(path, seen, x, searched):
                    return False
    
                seen.remove(x)
    
            searched.add(curr)
            return True

  • 0
    K

    cannot believe python is so fast!


  • 0
    O

    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.