Very concise 10-liner in Python. A couple of tiny tricks explained.


  • 1
    O
    class Solution(object):
        def findOrder(self, numCourses, prerequisites):
            edges, cnt = [[] for _ in range(numCourses)], [0]*numCourses
            for start,end in prerequisites:
                edges[end].append(start)
                cnt[start] += 1
            q = [x for x in range(numCourses) if cnt[x]==0]
            for node in q:
                for n in edges[node]:
                    cnt[n] -= 1
                    q += [n]*(cnt[n]==0)
            return q*(len(q)==numCourses)
    

    Which is equivalent to:

    class Solution(object):
        def findOrder(self, numCourses, prerequisites):
            edges = [[] for _ in range(numCourses)]
            cnt = [0 for _ in range(numCourses)]
            for start,end in prerequisites:
                edges[end].append(start)
                cnt[start] += 1
            ret = []
            q = collections.deque([x for x in range(numCourses) if cnt[x]==0])
            while q:
                node = q.popleft()
                ret.append(node)
                for n in edges[node]:
                    cnt[n] -= 1
                    if cnt[n] == 0:
                        q.append(n)
            return ret if len(ret)==numCourses else []
    

    This is a typical BFS topological sort, with some tiny tricks to make it short:

    1. the queue and the result list can be combined and become one list.
    2. List * Boolean is your best friend, like q*(len(q)==numCourses)

Log in to reply
 

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