CourseScheduleII解答

 1 public class Solution {
 2     public int[] findOrder(int numCourses, int[][] prerequisites) {
 3         // This problem is to print one possible topological sort result
 4         // First, we need to construct a directed graph in the form of adjacency list
 5         List[] adjacencyList = new ArrayList[numCourses]; 
 6         int[] result = new int[numCourses];
 7         int[] degree = new int[numCourses];
 8         Arrays.fill(degree, 0);
 9         for (int j = 0; j ) {
10             List tmpList = new ArrayList();
11             tmpList.add(j);
12             adjacencyList[j] = tmpList;
13         }
14         int length = prerequisites.length;
15         for (int j = 0; j ) {
16             int[] pair = prerequisites[j];
17             adjacencyList[pair[1]].add(pair[0]);
18             degree[pair[0]]++;
19         }
20         
21         // queue is to store nodes with 0 in-degree
22         Queue queue = new LinkedList();
23         for (int j = 0; j ) {
24             if (degree[j] == 0)
25                 queue.add(j);
26         }
27         if (queue.size() == 0)
28             return new int[0];
29         int i = 0;
30         
31         // begin bfs
32         while (queue.size() > 0) {
33             int current = queue.remove();
34             result[i] = current;
35             List currentList = adjacencyList[current];
36             for (int j = 1; j ) {
37                 int tmp = currentList.get(j);
38                 degree[tmp]--;
39                 if (degree[tmp] == 0)
40                     queue.add(tmp);
41             }
42             i++;
43         }
44         if (i < numCourses)
45             return new int[0];
46         return result;
47     }
48 }