# Short Java Solution

• ``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// topological sort
// preparation: a hashmap to represent the graph, and an array to keep indegrees of each vertex
HashMap<Integer, List<Integer>> G = new HashMap<>();
int[] indegrees = new int[numCourses];
for (int[] p : prerequisites) {
if (!G.containsKey(p[0])) {
G.put(p[0], new ArrayList<>());
}
indegrees[p[1]]++;
}
// perform topological sort until we have visited all courses
// whenever we have visited a course with indegree == 0, we set it to -1 so it won't be visited again
// it a topological sort exists, then we can visit all courses without return false
for (int i = 0; i < numCourses; i++) {
int course = -1;
for (int j = 0; j < indegrees.length; j++) {
if (indegrees[j] == 0) {
course = j;
indegrees[j] = -1;
break;
}
}
if (course == -1) {
return false;
}
// course can be no prerequisite and doesn't exist in HashMap
if (G.get(course) != null) {
for (int c : G.get(course)) {
indegrees[c]--;
}
}
}
return true;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.