210.md

Courses Schedule II

Description

link

---

Solution1 : BFS

• Topological Sorting

---

Code 1

Complexity T : O(V + E) M : O(V + E)

class Solution:
    def findOrder(self, n, edges):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        graph = collections.defaultdict(set)
        in_degree = [0] * n
        
        for edge in edges:
            graph[edge[0]].add(edge[1])
            in_degree[edge[1]] += 1
        
        visited = []
        q = collections.deque()
        
        for i in range(n):
            if in_degree[i] == 0:
                q.append(i)
        
        while q:
            x = q.popleft()
            visited.append(x)
            for i in graph[x]:
                in_degree[i] -= 1
                if in_degree[i] == 0:
                    q.append(i)
        
        return visited[::-1] if len(visited) == n else []

Solution1 : DFS

• See Code

---

Code 2

Complexity T : O(V + E) worst situation

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        # dic[i] is the indegree of the node i,  computing will be faster
        dic  = [0 for i in range(numCourses)];
        neigh = collections.defaultdict(set)
        for i, j in prerequisites:
            dic[i] += 1;
            neigh[j].add(i)
        stack  = [i for i in range(numCourses) if dic[i] == 0];
        res = []
        while stack:
            node = stack.pop()
            res.append(node)
            for i in neigh[node]:
                dic[i] -= 1
                if dic[i] == 0:
                    stack.append(i)
        for i in range(numCourses):
            if dic[i] > 0:
                return [];
        return res