leetcode 207: Course Schedule

leetcode 207: Course Schedule

Course Schedule

There are a total of n courses you have to take, labeled from 0 ton - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:[0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more abouthow a graph is represented.

[思路]

此問題等價於 圖(or forest)中有無環的存在.

使用topological sorting, 成功sort後,如果prerequisite沒有空,則沒有環.

[CODE]

public class Solution {
    // [4, 3] [3,2] [2,1]
    //init check.
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Set pre = new HashSet();
        for(int[] e : prerequisites) {
            pre.add(e);
        }
        
        int n = pre.size();
        if(n > numCourses*(numCourses-1)/2) return false;
        
        while(!getEnds(pre).isEmpty() ){};
        return pre.isEmpty();
    }
    // [1,2] [2, 3] [3,4]
    private Set getEnds(Set pre) {
        Set set = new HashSet();
        for(int[] arr : pre) {
            set.add(arr[0]);
        }
        
        for(int[] arr: pre) {
            set.remove(arr[1]);
        }
        
        Iterator iter = pre.iterator();  
        while(iter.hasNext() ) {
            int[] arr = iter.next();
            if(set.contains(arr[0]) ) iter.remove();
        }
        return set;
    }
}