Topological Sort in JAVA

  • 0

    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++) 
            map.put(i, new LinkedList<Integer>());
            for(int[] edge : prerequisites){
            Queue<Integer> zeroVerts = new LinkedList<Integer>(); //determine all vertices with zero in-degree
            for(int i = 0; i < numCourses; i++)
                if(indegree[i] == 0) 
            int courseOrder = 0; //number of courses could be put into the topological order
                int course = zeroVerts.poll(); //choose a vertex with 0 in-degree
    	        for(int c : map.get(course)){ //"remove" vertex by updating its neighbors
    	            if(indegree[c] == 0) //add any vertex that now has 0 in-degree to the queue
            return courseOrder == numCourses; //if we haven't added all of the vertices to the topo order, there's a cycle

Log in to reply

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