course schedule


Course Schedule I

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
public boolean (int numCourses, int[][] prerequisites) {
if (numCourses <= 1)
return true;
HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
int[] inlink = new int[numCourses];
for (int i = 0; i < prerequisites.length; ++i) {
int u = prerequisites[i][1], v = prerequisites[i][0];
if (graph.containsKey(u)) {
if (graph.get(u).contains(v))
continue;
inlink[v] += 1;
graph.get(u).add(v);
} else {
HashSet<Integer> set = new HashSet<>();
inlink[v] += 1;
set.add(v);
graph.put(u, set);
}
}
return bfs(graph, inlink);
}

public boolean bfs(HashMap<Integer, HashSet<Integer>> graph, int[] inlink) {
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < inlink.length; ++i) {
if (inlink[i] == 0)
q.offer(i);
}
while (!q.isEmpty()) {
int u = q.poll();
if (graph.containsKey(u) == false) {
continue;
}
for (int v : graph.get(u)) {
inlink[v] -= 1;
if (inlink[v] == 0) {
q.offer(v);
}
}
}
for (int i : inlink)
if (i > 0)
return false;
return true;
}

Course Schedule II

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
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses <= 1)
return new int[1];
HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
int[] inlink = new int[numCourses];
for (int i = 0; i < prerequisites.length; ++i) {
int u = prerequisites[i][1], v = prerequisites[i][0];
if (graph.containsKey(u)) {
if (graph.get(u).contains(v))
continue;
inlink[v] += 1;
graph.get(u).add(v);
} else {
inlink[v] += 1;
HashSet<Integer> set = new HashSet<>();
set.add(v);
graph.put(u, set);
}
}
return bfs(graph, inlink);
}
public int[] bfs(HashMap<Integer, HashSet<Integer>> graph, int[] inlink) {
int[] ans = new int[inlink.length];
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < inlink.length; ++i) {
if (inlink[i] == 0)
q.offer(i);
}
int index = 0;
while (!q.isEmpty()) {
int u = q.poll();
ans[index++] = u;
if (graph.containsKey(u) == false)
continue;
for (int i : graph.get(u)) {
inlink[i] -= 1;
if (inlink[i] == 0)
q.offer(i);
}
}
for (int i : inlink) {
if (i != 0)
return new int[0];
}
return ans;
}