# Topological Sort in JAVA

• I use HashMap to store the list of adjacent vertices (courses).
The comments are included, hope it helps!

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegree = new int[numCourses]; //record the in-degree of each vertex
HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>(); //map each vertex to its list of adjacent vertices
for(int i = 0; i < numCourses; i++)
for(int[] edge : prerequisites){
indegree[edge[0]]++;
}
Queue<Integer> zeroVerts = new LinkedList<Integer>(); //determine all vertices with zero in-degree
for(int i = 0; i < numCourses; i++)
if(indegree[i] == 0)
zeroVerts.offer(i);
int courseOrder = 0; //number of courses could be put into the topological order
while(!zeroVerts.isEmpty()){
int course = zeroVerts.poll(); //choose a vertex with 0 in-degree
courseOrder++;
for(int c : map.get(course)){ //"remove" vertex by updating its neighbors
indegree[c]--;
if(indegree[c] == 0) //add any vertex that now has 0 in-degree to the queue
zeroVerts.offer(c);
}
}
return courseOrder == numCourses; //if we haven't added all of the vertices to the topo order, there's a cycle
}
}
``````

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