Course Schedule

这个就拓扑查环,没啥说的

class Solution {
    public boolean canFinish(int n, int[][] p) {
        int[] into = new int[n];
        for(int[] pp : p)
            into[pp[0]]++;
         for(int k = 0; k < n; k++)
        {
            int i = 0;
            while(i < n)
            {
                if(into[i] == 0)
                    break;
                i++;
            }
            if(i == n)
                return false;
            into[i] = -1; //visited
            for(int[] pp : p)
                if(pp[1] == i)
                    into[pp[0]]--;
        }
        return true;
    }
}

BFS 方法, 通过入度判断环.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, HashSet<Integer>> map = new HashMap<>();
        int[] ind = new int[numCourses]; 
        for(int[] p : prerequisites){
            if(!map.containsKey(p[1]))
                map.put(p[1], new HashSet<Integer>());
            map.get(p[1]).add(p[0]); 
            ind[p[0]]++;
        }  
        Queue<Integer> queue = new LinkedList<>();
        int count = 0;
        for(int i = 0; i < numCourses; i++)
            if(ind[i] == 0)
                queue.add(i);  
        while(!queue.isEmpty()){
            int n = queue.poll();
            count++;
            for(int nn : map.getOrDefault(n, new HashSet<Integer>())){
                ind[nn]--;
                if(ind[nn] == 0)
                    queue.add(nn);
            }
        }
        return count == numCourses;
    }
}