#Problem

#⭐️⭐️

Course Schedule

#Solution

Topological Sort

#Code

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
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses == 0) return true;
if (prerequisites.length == 0) return true;
final Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
graph.put(i, new HashSet<>());
}
for (final int[] edge : prerequisites) {
graph.get(edge[0]).add(edge[1]);
}
final int[] visited = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0) {
if (dfsTopoSort(i, visited, graph)) {
return false;
}
}
}
for (final int v : visited) {
if (visited[v] != 1) return false;
}
return true;
}
private boolean dfsTopoSort(final int v, final int[] visited, final Map<Integer, Set<Integer>> graph) {
if (visited[v] == -1) return true;
if (visited[v] == 1) return false;
visited[v] = -1;
for (final int adj : graph.get(v)) {
if(dfsTopoSort(adj, visited, graph)) {
return true;
}
}
visited[v] = 1;
return false;
}
}

Comments