Easy to understand JAVA:)


  • 0
    S
       public boolean canFinish(int numCourses, int[][] prerequisites) {
            int[][] matrix = new int[numCourses][numCourses];
            int[] indegree = new int[numCourses];
            
            for(int i=0; i<prerequisites.length; i++) {
                if(matrix[prerequisites[i][0]][prerequisites[i][1]] == 1) { //for duplicate input like [1,9][1,9]
                    continue;
                }
                matrix[prerequisites[i][0]][prerequisites[i][1]] = 1;
                indegree[prerequisites[i][1]]++;
            }
            
            Queue<Integer> queue = new LinkedList<>();
            int numOfInDegreeZero = 0;
            for(int i=0;i<numCourses;i++) {
                if(indegree[i]==0) {
                    queue.offer(i);
                    numOfInDegreeZero++;
                }
            }
            while(!queue.isEmpty()) {
                int cur = queue.poll();
                for(int i=0;i<numCourses; i++) {
                    if(matrix[cur][i] == 1) {
                        indegree[i]--;
                        if(indegree[i]==0) {
                            queue.offer(i);
                            numOfInDegreeZero++;
                        }
                    }
                }
            }
            
            return numOfInDegreeZero == numCourses;
        }

Log in to reply
 

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