JAVA---------Easy Version To UnderStand!!!!!!!!!!!!!!!!!


  • 43
    H
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
    	if (numCourses <= 0)
    		return false;
    	Queue<Integer> queue = new LinkedList<>();
    	int[] inDegree = new int[numCourses];
    	for (int i = 0; i < prerequisites.length; i++) {
    		inDegree[prerequisites[i][1]]++;
    	}
    	for (int i = 0; i < inDegree.length; i++) {
    		if (inDegree[i] == 0)
    			queue.offer(i);
    	}
    	while (!queue.isEmpty()) {
    		int x = queue.poll();
    		for (int i = 0; i < prerequisites.length; i++) {
    			if (x == prerequisites[i][0]) {
    				inDegree[prerequisites[i][1]]--;
    				if (inDegree[prerequisites[i][1]] == 0)
    					queue.offer(prerequisites[i][1]);
    			}
    		}
    	}
    	for (int i = 0; i < inDegree.length; i++) {
    		if (inDegree[i] != 0)
    			return false;
    	}
    	return true;
    }

  • 0
    J

    Thanks, this solution is very good!


  • 0
    H

    thanks,please vote me for this problem!!!


  • 8
    A

    Line 7:
    is inDegree[prerequisites[i][1]]++; correct?
    i think it should be inDegree[prerequisites[i][0]]++;


  • 0
    R

    Can anybody explain to me why this solution work? Are there any theories about the indegree and outdegree which support this solution?


  • 0
    C

    @alpit I think you are right. I am confused for a long time.


  • 0
    Y

    Very easy to understand, except for the mistake which @alpit already mentioned above. However the Time complexity is not good.


Log in to reply
 

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