leetcode210. Schedule II 207 Curriculum topology sorting DFS BFS

A topological sort

For a directed acyclic graph (Directed Acyclic Graph abbreviation DAG)G Topological sort , Yes, it will G All the vertices in are arranged in a linear sequence , Make any pair of vertices in the graph u and v, Ruobian <u,v>∈E(G), be u In a linear sequence v Before . Usually , Such a linear sequence is called satisfying topological order (Topological Order) Sequence , Short for topological sequence . To put it simply , From a partial order on a set, we get a complete order on the set , This operation is called topological sorting .

Title Description

210. The curriculum II
     Now you have numCourses Courses need to be selected , Write it down as 0 To numCourses - 1. Give you an array prerequisites , among prerequisites[i] = [ai, bi] , In elective courses ai front must First elective bi .

for example , Want to learn the course 0 , You need to finish the course first 1 , We use a match to represent ：[0,1] .
Return to the learning order you arranged to complete all the courses . There may be more than one correct order , You just go back Any one That's all right. . If it is not possible to complete all the courses , return An empty array .

Example 1：

Input ：numCourses = 2, prerequisites = [[1,0]]
Output ：[0,1]
explain ： All in all 2 Courses . To learn the course 1, You need to finish the course first 0. therefore , The correct order of courses is [0,1] .
Example 2：

Input ：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output ：[0,2,1,3]
explain ： All in all 4 Courses . To learn the course 3, You should finish the course first 1 And courses 2. And the curriculum 1 And courses 2 They should all be in the class 0 after .
therefore , A correct sequence of courses is [0,1,2,3] . The other right sort is [0,2,1,3] .
Example 3：

Input ：numCourses = 1, prerequisites = []
Output ：[0]

Tips ：
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
all [ai, bi] Different from each other

Solution ideas

The title gives a directed graph , We get topological ordering , Is the final solution
dfs

#dfs
class Solution:
    
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        ans=[]
        valid=True
        visited=[0]*numCourses
        edges=collections.defaultdict(list)
        for pre in prerequisites:
            edges[pre[1]].append(pre[0])
        
        def dfs(course):
            nonlocal valid
            visited[course]=1
            for next_course in edges[course]:
                if not valid:
                    return
                if visited[next_course]==0:
                    dfs(next_course)
                elif visited[next_course]==1:
                    valid=False
                    return
                    
            visited[course]=2
            ans.append(course)
        for course in range(numCourses):
            if visited[course]==0:
                dfs(course)
            if not valid:
                break
        if valid:
            return ans[::-1]
        else:
            return []

bfs

#bfs
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        from collections import deque
        q=deque()
        in_counts=[0]*numCourses
        edges=collections.defaultdict(list)
        ans=[]
        for pre in prerequisites:
            edges[pre[1]].append(pre[0])
            in_counts[pre[0]]+=1
        for i,in_count in enumerate(in_counts):
            if in_count==0:
                q.appendleft(i)
        while q:
            course=q.pop()
            ans.append(course)
            for next_course in edges[course]:
                #print(in_counts)
                in_counts[next_course]-=1
                if in_counts[next_course]==0:
                    q.appendleft(next_course)
        if len(ans)==numCourses:
            return ans
        else:
            return []