LeetCode/src/hard/CourseScheduleII.java at master · chenyiAlone/LeetCode · GitHub

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package hard;

import java.util.*;
/**
 * ClassName: CourseScheduleII.java
 * Auther: chenyiAlone
 * Create Time: 2019/5/8 17:05
 * Description: No.210
 * 思路:
 *      1. Adjacency Matrix + HashSet
 *      2. index used to count with point that was searched
 *          if index < numCourses
 *              figure has a ring
 *          else
 *              at least one case
 *
 *
 *
 *
 * There are a total of n courses you have to take, labeled from 0 to n-1.
 *
 * Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
 *
 * Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
 *
 * There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
 *
 * Example 1:
 *
 * Input: 2, [[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: 4, [[1,0],[2,0],[3,1],[3,2]]
 * Output: [0,1,2,3] or [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] .
 * Note:
 *
 * The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
 * You may assume that there are no duplicate edges in the input prerequisites.
 *
 */
public class CourseScheduleII {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        boolean[][] graph = new boolean[numCourses][numCourses];
        int[] degree = new int[numCourses];
        for (int[] prere : prerequisites) {
            int start = prere[1], end = prere[0];
            graph[start][end] = true;
            degree[end] += 1;
        }
        Queue<Integer> que = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (degree[i] == 0)
                que.offer(i);
        }
        int index = 0;
        while (!que.isEmpty()) {
            int v = que.poll();
            for (int i = 0; i < numCourses; i++) {
                if (graph[v][i]) {
                    degree[i] -= 1;
                    if (degree[i] == 0)
                        que.offer(i);
                }
            }
            if (index < numCourses)
                res[index++] = v;
            else
                break;
        }
        if (index < numCourses)
            return new int[]{};
        return res;
    }
}