Depth-First Search
Breadth-First Search
Graph
Topological Sort
Description
There are a total of numCourses
courses you have to take, labeled from 0
to numCourses - 1
. You are given an array prerequisites
where prerequisites[i] = [ai , bi ]
indicates that you must take course bi
first if you want to take course ai
.
For example, the pair [0, 1]
, indicates that to take course 0
you have to first take course 1
.
Return the ordering of courses you should take to finish all courses . If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array .
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
Example 2:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
Example 3:
Input: numCourses = 1, prerequisites = []
Output: [0]
Constraints:
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai , bi < numCourses
ai != bi
All the pairs [ai , bi ]
are distinct .
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def findOrder ( self , numCourses : int , prerequisites : List [ List [ int ]]) -> List [ int ]:
g = defaultdict ( list )
indeg = [ 0 ] * numCourses
for a , b in prerequisites :
g [ b ] . append ( a )
indeg [ a ] += 1
ans = []
q = deque ( i for i , x in enumerate ( indeg ) if x == 0 )
while q :
i = q . popleft ()
ans . append ( i )
for j in g [ i ]:
indeg [ j ] -= 1
if indeg [ j ] == 0 :
q . append ( j )
return ans if len ( ans ) == numCourses else []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 class Solution {
public int [] findOrder ( int numCourses , int [][] prerequisites ) {
List < Integer >[] g = new List [ numCourses ] ;
Arrays . setAll ( g , k -> new ArrayList <> ());
int [] indeg = new int [ numCourses ] ;
for ( var p : prerequisites ) {
int a = p [ 0 ] , b = p [ 1 ] ;
g [ b ] . add ( a );
++ indeg [ a ] ;
}
Deque < Integer > q = new ArrayDeque <> ();
for ( int i = 0 ; i < numCourses ; ++ i ) {
if ( indeg [ i ] == 0 ) {
q . offer ( i );
}
}
int [] ans = new int [ numCourses ] ;
int cnt = 0 ;
while ( ! q . isEmpty ()) {
int i = q . poll ();
ans [ cnt ++] = i ;
for ( int j : g [ i ] ) {
if ( -- indeg [ j ] == 0 ) {
q . offer ( j );
}
}
}
return cnt == numCourses ? ans : new int [ 0 ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 class Solution {
public :
vector < int > findOrder ( int numCourses , vector < vector < int >>& prerequisites ) {
vector < vector < int >> g ( numCourses );
vector < int > indeg ( numCourses );
for ( auto & p : prerequisites ) {
int a = p [ 0 ], b = p [ 1 ];
g [ b ]. push_back ( a );
++ indeg [ a ];
}
queue < int > q ;
for ( int i = 0 ; i < numCourses ; ++ i ) {
if ( indeg [ i ] == 0 ) {
q . push ( i );
}
}
vector < int > ans ;
while ( ! q . empty ()) {
int i = q . front ();
q . pop ();
ans . push_back ( i );
for ( int j : g [ i ]) {
if ( -- indeg [ j ] == 0 ) {
q . push ( j );
}
}
}
return ans . size () == numCourses ? ans : vector < int > ();
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 func findOrder ( numCourses int , prerequisites [][] int ) [] int {
g := make ([][] int , numCourses )
indeg := make ([] int , numCourses )
for _ , p := range prerequisites {
a , b := p [ 0 ], p [ 1 ]
g [ b ] = append ( g [ b ], a )
indeg [ a ] ++
}
q := [] int {}
for i , x := range indeg {
if x == 0 {
q = append ( q , i )
}
}
ans := [] int {}
for len ( q ) > 0 {
i := q [ 0 ]
q = q [ 1 :]
ans = append ( ans , i )
for _ , j := range g [ i ] {
indeg [ j ] --
if indeg [ j ] == 0 {
q = append ( q , j )
}
}
}
if len ( ans ) == numCourses {
return ans
}
return [] int {}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 function findOrder ( numCourses : number , prerequisites : number [][]) : number [] {
const g : number [][] = Array . from ({ length : numCourses }, () => []);
const indeg : number [] = new Array ( numCourses ). fill ( 0 );
for ( const [ a , b ] of prerequisites ) {
g [ b ]. push ( a );
indeg [ a ] ++ ;
}
const q : number [] = [];
for ( let i = 0 ; i < numCourses ; ++ i ) {
if ( indeg [ i ] === 0 ) {
q . push ( i );
}
}
const ans : number [] = [];
while ( q . length ) {
const i = q . shift () ! ;
ans . push ( i );
for ( const j of g [ i ]) {
if ( -- indeg [ j ] === 0 ) {
q . push ( j );
}
}
}
return ans . length === numCourses ? ans : [];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 impl Solution {
pub fn find_order ( num_courses : i32 , prerequisites : Vec < Vec < i32 >> ) -> Vec < i32 > {
let n = num_courses as usize ;
let mut adjacency = vec! [ vec! []; n ];
let mut entry = vec! [ 0 ; n ];
// init
for iter in prerequisites . iter () {
let ( a , b ) = ( iter [ 0 ], iter [ 1 ]);
adjacency [ b as usize ]. push ( a );
entry [ a as usize ] += 1 ;
}
// construct deque & reslut
let mut deque = std :: collections :: VecDeque :: new ();
for index in 0 .. n {
if entry [ index ] == 0 {
deque . push_back ( index );
}
}
let mut result = vec! [];
// bfs
while ! deque . is_empty () {
let head = deque . pop_front (). unwrap ();
result . push ( head as i32 );
// update degree of entry
for & out_entry in adjacency [ head ]. iter () {
entry [ out_entry as usize ] -= 1 ;
if entry [ out_entry as usize ] == 0 {
deque . push_back ( out_entry as usize );
}
}
}
if result . len () == n {
result
} else {
vec! []
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 public class Solution {
public int [] FindOrder ( int numCourses , int [][] prerequisites ) {
var g = new List < int > [ numCourses ];
for ( int i = 0 ; i < numCourses ; ++ i ) {
g [ i ] = new List < int > ();
}
var indeg = new int [ numCourses ];
foreach ( var p in prerequisites ) {
int a = p [ 0 ], b = p [ 1 ];
g [ b ]. Add ( a );
++ indeg [ a ];
}
var q = new Queue < int > ();
for ( int i = 0 ; i < numCourses ; ++ i ) {
if ( indeg [ i ] == 0 ) {
q . Enqueue ( i );
}
}
var ans = new int [ numCourses ];
var cnt = 0 ;
while ( q . Count > 0 ) {
int i = q . Dequeue ();
ans [ cnt ++ ] = i ;
foreach ( int j in g [ i ]) {
if ( -- indeg [ j ] == 0 ) {
q . Enqueue ( j );
}
}
}
return cnt == numCourses ? ans : new int [ 0 ];
}
}