A simple Java solution with Queue


  • 6
    J
    public static int[] findOrder(int numCourses, int[][] prerequisites) {
    	int[] result = new int[numCourses];
    	int[] preCnt = new int[numCourses];
    	List<Integer>[] nextSet = new List[numCourses];
    	for(int i=0; i<numCourses; i++)
    		nextSet[i] = new ArrayList<>();
    
    	for(int[] p : prerequisites) {
    		preCnt[p[0]]++;
    		nextSet[p[1]].add(p[0]);
    	}
    
    	Queue<Integer> sourceNode = new LinkedList<Integer>();
    	for(int i=0; i<numCourses; i++)
    		if(preCnt[i] == 0)
    			sourceNode.add(i);
    	
    	for(int i=0; i<numCourses; i++) {
    		if(sourceNode.isEmpty())
    			return new int[0];
    		int n = sourceNode.poll();
    		result[i] = n;
    		for(int next : nextSet[n]) {
    			preCnt[next]--;
    			if(preCnt[next] == 0)
    				sourceNode.add(next);
    		}
    	}
    	return result;
    }
    

    Here we keep adding those nodes has no incoming vertex source node. And once it's added, it will be removed from the graph and update the preCnt of the destination nodes. I use preCnt[i] to keep track the number of incomming vertex and use queue sourceNode to keep track the remain source node.


  • 0

    Very slick and efficient. We can also use while when polling & adding the queue.


Log in to reply
 

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