Simple Java Solution


  • 0
    Z
    import java.util.LinkedList;
    
    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            LinkedList<Integer> queue = new LinkedList<>();
            int[] indegree = new int[numCourses];
    
            for (int i = 0; i < prerequisites.length; i++) {
                indegree[prerequisites[i][0]]++;
            }
    
            for (int i = 0; i < numCourses; i++) {
                if(indegree[i] == 0){
                    queue.offer(i);
                }
            }
    
            int count = 0;
            while (!queue.isEmpty()){
                int course = queue.poll();
                count++;
                for (int i = 0; i < prerequisites.length; i++) {
                    if(prerequisites[i][1] == course){
                        indegree[prerequisites[i][0]]--;
                        if(indegree[prerequisites[i][0]] == 0){
                            queue.offer(prerequisites[i][0]);
                        }
                    }
                }
            }
     
            return count == numCourses;
        }
    }
    

  • 0
    M

    I guess you meant outdegree. I like this approach and this seems to reduce the run time drastically. Do you have any idea of the run time of this algorithm?


  • 0
    Z

    @Mino-De It is topological sort and It is indegree, for example [5,6] (6->5), so indegree[5]++.
    I think it's time complexity is O(n^2).


  • 0
    M

    @zhangsan My bad. Looks like i got the question the other way around. Thanks.


Log in to reply
 

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