Easy understand java AC 60ms


  • 0
    W

    public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
    int ret[] = new int[numCourses];
    if(prerequisites == null) return new int[0];

        int len = prerequisites.length;
        //if there is no prerequisites, return a sequence of courses
        if(len == 0){
            int[] res = new int[numCourses];
            for(int m=0; m<numCourses; m++){
                res[m]=m;
            }
            return res;
        }
        
        int[] vertex = new int[numCourses];
        for(int[] pair : prerequisites) {
            vertex[pair[0]]++;
        }
        
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i = 0; i < numCourses; i++) {
            if(vertex[i] == 0) {
                q.offer(i);
            }
        }
        int select = 0;
        while(!q.isEmpty()) {
            int c = q.poll();
            ret[select++] = c;
            for(int[] pair : prerequisites) {
                if(pair[1] == c) {
                    if(--vertex[pair[0]] == 0) {
                        q.offer(pair[0]);
                    }
                }
            }
        }
        
        return select == numCourses ? ret: new int[0];
    }
    

    }


Log in to reply
 

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