# 207. Course Schedule

###### tags: `leetcode`,`graph`,`dfs`,`medium`

>ref: https://leetcode.com/problems/binary-search/
>


>Constraints:
1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.

### dfs

>1. tc: O(n+e) visit all node once, and visit each edge once
>2. sc: O(n+e)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        // class preclass  , if 
        Map<Integer,List<Integer>> hash= new HashMap<>();

        // build graph
        for(int[] pre:prerequisites){
            hash.computeIfAbsent(pre[0],a->new ArrayList<>()).add(pre[1]);
        }

        Set<Integer> checked= new HashSet<>();
        Set<Integer> visited= new HashSet<>();

        for(int i=0;i<numCourses;i++){
            if(cycle(checked,visited,i,hash)){
                return false;
            }
        }


        return true;
        
    }

    private boolean cycle(Set<Integer> checked,Set<Integer> visited,int idx,Map<Integer,List<Integer>> hash){

        if(checked.contains(idx))return false;
        if(visited.contains(idx))return true;

        visited.add(idx); // backtrack

        for(int nei: hash.getOrDefault(idx,new ArrayList<>())){
            if(cycle(checked,visited,nei,hash)){
                return true;
            }
        }

        visited.remove(idx);// backtrack

        checked.add(idx); // memo idx is no cyclic, if a->b and b->a the dfs will find it

        return false;

    }
}

### topo sort

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        //topo sort

        //tc n+e
        //sc n+e

        // class preclass  , if 
        Map<Integer,List<Integer>> hash= new HashMap<>();

        int[] topo = new int[numCourses]; // record how many preclass need

        // build graph
        for(int[] pre:prerequisites){
            hash.computeIfAbsent(pre[1],a->new ArrayList<>()).add(pre[0]);// record class: postclass
            topo[pre[0]]++;
        }

        Queue<Integer> q= new LinkedList<>();

        for(int i=0;i<numCourses;i++){
            if(topo[i]==0){
                q.add(i);
            }
        }

        while(!q.isEmpty()){
            int i=q.poll();
            for(int postclass:hash.getOrDefault(i,new ArrayList<>())){
                topo[postclass]--;  // remove preclass count

                if(topo[postclass]==0){
                    q.offer(postclass);
                }
            }
        }

        for(int left:topo){
            if(left!=0)return false; // the class cannot be reach
        }


        return true;
        
    }

}