207. Course Schedule

Question

There are a total of n courses you have to take, labeled from 0 to n-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?

Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: 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.

Thinking:

• Method：拓扑图， bfs
  • 先构造邻接表，将所有入度为0的结点都加入队列中。
  • 按序取出所结点，最后无法被取出的说明造成了环路，永远都会有入度并且无法消除。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        int[] indegree = new int[numCourses];
        int count = 0;
        for(int i = 0; i < prerequisites.length; i++){
            int first = prerequisites[i][0];
            int second = prerequisites[i][1];
            if(!adj.containsKey(first))
                adj.put(first, new ArrayList<Integer>());
            adj.get(first).add(second);
            indegree[second] ++;
        }
        LinkedList<Integer> q = new LinkedList<>();
        for(int i = 0; i < numCourses; i++)
            if(indegree[i] == 0)
                q.add(i);
        while(!q.isEmpty()){
            Integer pre = q.poll();
            System.out.println(pre);
            count ++;
            List<Integer> temp = null;
            if(adj.containsKey(pre)){
                temp = adj.get(pre);
                for(Integer num : temp){
                    indegree[num] --;
                    if(indegree[num] == 0)
                        q.add(num);
                }
            }
        }
        return count == numCourses;
    }
}

二刷

1. Method 1： We can use Khan method to solve this question, which is another version of bfs.

   class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for(int[] pre : prerequisites){
            List<Integer> temp = adj.containsKey(pre[0]) ? adj.get(pre[0]) : new ArrayList<Integer>();
            temp.add(pre[1]);
            adj.put(pre[0], temp);
            indegree[pre[1]]++;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            if(indegree[i] == 0)  queue.add(i);
        }
        int count = 0;
        while(!queue.isEmpty()){
            int pre = queue.poll();
            count++;
            if(adj.containsKey(pre)){
                List<Integer> list = adj.get(pre);
                for(Integer v : list){
                    indegree[v]--;
                    if(indegree[v] == 0)
                        queue.add(v);
                }
            }
        }
        return count == numCourses;
    }
   }
   

2. Method 2: Use dfs to solve this problem.

   class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        Map<Integer, List<Integer>> adj = new HashMap<>();
        boolean[] visited = new boolean[numCourses];
        for(int[] pre : prerequisites){
            indegree[pre[1]]++;
            List<Integer> temp = adj.containsKey(pre[0]) ? adj.get(pre[0]): new ArrayList<>();
            temp.add(pre[1]);
            adj.put(pre[0], temp);
        }
        boolean containsZero = false;
        for(int i = 0; i < numCourses; i++){
            if(indegree[i] == 0 && !visited[i]){
                containsZero = true;
                dfs(i, indegree, visited, adj);
            }
        }
        if(!containsZero) return false;
        for(boolean visit : visited){
            if(!visit) return false;
        }
        return true;
    }
    private void dfs(int cur, int[] indegree, boolean[] visited, Map<Integer, List<Integer>> adj){
        visited[cur] = true;
        if(adj.containsKey(cur)){
            for(Integer next : adj.get(cur)){
                indegree[next]--;
                if(indegree[next] == 0 && !visited[next]){
                    dfs(next, indegree, visited, adj);
                }
            }
        }
    }
   }
   

Reference

1. 【图论】有向无环图的拓扑排序