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; } }
        
       
      
     
    
   
  

?

?