210. Course Schedule II

main.py

class Solution(object):
    def findOrder(self, num_courses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        # basically this is Kahn algorithm for topological sorting
        # I like it because it depends on the indegree centrality of the node
        degrees = collections.defaultdict(int)
        g = collections.defaultdict(list)
        
        for p in prerequisites:
            g[p[1]].append(p[0])
            degrees[p[0]] += 1
        
        q = deque()
        
        for i in range(num_courses):
            if i not in degrees or degrees[i] == 0:
                q.append(i)
        result = []
        while q:
            c = q.popleft()
            for v in g[c]:
                degrees[v] -= 1        
                if degrees[v] == 0:
                    q.append(v)
            result.append(c)
        if len(result) != num_courses:
            return []
        else:
            return result