Python solution, passed once with 860 ms run time, TLE in other attempts


  • 0
    S

    The code is:

    def canFinish(self, numCourses, prerequisites):
        d = {}
        for i in xrange(numCourses):
            d[i] = set()
        for p in prerequisites:
            for j in xrange(1, len(p)):
                d[p[j]].add(p[j - 1])
        c = range(numCourses)
        while len(c):
            i = 0
            l = len(c) - 1
            while True:
                t = c[i]
                if not len(d[t]):
                    c.remove(t)
                    for j in c:
                        d[j].discard(t)
                    break
                elif i == l:
                    return False
                i += 1
        return True

  • 0
    S

    Finally got the algorithm working, but the native solution 10 times slower than the solutions from the task hints:

    def canFinish(self, numCourses, prerequisites):
        d = [set() for i in xrange(numCourses)]
        for i, j in prerequisites:
            d[j].add(i)
        l = [len(d[i]) for i in xrange(numCourses)]
        f = [True for i in xrange(numCourses)]
        n = numCourses
        while n:
            ver = [i for i in xrange(numCourses) if not l[i] and f[i]]
            if not len(ver):
                return False
            n -= len(ver)
            for v in ver:
                f[v] = False
                for i in xrange(numCourses):
                    if f[i] and v in d[i]:
                        l[i] -= 1
        return True

Log in to reply
 

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