-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leetcode0210.java
90 lines (85 loc) · 2.83 KB
/
Leetcode0210.java
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
82
83
84
85
86
87
88
89
90
package com.dezhonger.le;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by dezhonger on 2019/12/12
*
* @author dezhonger
* @since 2019/12/12
*/
public class Leetcode0210 {
public static void main(String[] args) {
System.out.println(Arrays.toString(new Leetcode0210().findOrder(2, new int[][]{
{1, 0}
})));
}
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[][] matrix = new int[numCourses][numCourses]; // i -> j
int[] indegree = new int[numCourses];
for (int i = 0; i < prerequisites.length; i++) {
int ready = prerequisites[i][0];
int pre = prerequisites[i][1];
if (matrix[pre][ready] == 0) //多重边
indegree[ready]++;
matrix[pre][ready] = 1;
}
int count = 0;
int[] res = new int[numCourses];
Queue<Integer> queue = new LinkedList();
//所有入度为0的点
for (int i = 0; i < indegree.length; i++) {
if (indegree[i] == 0) queue.offer(i);
}
while (!queue.isEmpty()) {
int course = queue.poll();
res[count] = course;
count++; //已经学完的课程
for (int i = 0; i < numCourses; i++) {
if (matrix[course][i] != 0) {
//编号为i的课程的先修课程都已经学完
if (--indegree[i] == 0)
queue.offer(i);
}
}
}
if (count == numCourses) {
return res;
} else {
return new int[0];
}
}
//
// public boolean canFinish(int numCourses, int[][] prerequisites) {
// int[][] matrix = new int[numCourses][numCourses]; // i -> j
// int[] indegree = new int[numCourses];
//
// for (int i = 0; i < prerequisites.length; i++) {
// int ready = prerequisites[i][0];
// int pre = prerequisites[i][1];
// if (matrix[ready][pre] == 0) //多重边
// indegree[pre]++;
// matrix[ready][pre] = 1;
// }
//
//
// int count = 0;
// Queue<Integer> queue = new LinkedList();
// //所有入度为0的点
// for (int i = 0; i < indegree.length; i++) {
// if (indegree[i] == 0) queue.offer(i);
// }
// while (!queue.isEmpty()) {
// int course = queue.poll();
// count++; //已经学完的课程
// for (int i = 0; i < numCourses; i++) {
// if (matrix[course][i] != 0) {
// //编号为i的课程的先修课程都已经学完
// if (--indegree[i] == 0)
// queue.offer(i);
// }
// }
// }
// return count == numCourses;
// }
}