Regular topological problem with 7ms solution


  • 0
    Y
        ArrayList[] edges = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        for(int i = 0; i<numCourses;i++){
            edges[i] = new ArrayList<Integer>();
        }
        //initial edge list and indegree array
        for(int i = 0; i<prerequisites.length;i++){
            int start = prerequisites[i][1];
            int end = prerequisites[i][0];
            edges[start].add(end);
            indegree[end]++;
        }
        ArrayDeque<Integer> queue = new ArrayDeque();
        for(int i = 0; i<numCourses;i++){
            if(indegree[i] == 0) queue.offer(i);
        }
        //here, if no vertex has indegree 0, means there is a circle in it
        //no solution here is available to return;
        if(queue.isEmpty()) return new int[]{};
        int[] res = new int[numCourses];
        int idx = 0;
        while(!queue.isEmpty()){
            int top = queue.poll();
            res[idx++] = top;
            for(int i = 0; i<edges[top].size();i++){
                int v = (int)edges[top].get(i);
                indegree[v]--;
                if(indegree[v] == 0){
                    queue.offer(v);
                }
            }
        }
        return (idx == numCourses)? res : new int[]{};

Log in to reply
 

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