Algorithm-and-Leetcode/leetcode/207. Course Schedule.md at master

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

二刷

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

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

Third Time

Method 1: Topological sort + bfs

 class Solution {
 	public boolean canFinish(int numCourses, int[][] prerequisites) {
 		Map<Integer, List<Integer>> map = new HashMap<>();
 		int[] indegree = new int[numCourses];
 		Set<Integer> remain = new HashSet<>();
 		for(int i = 0; i < numCourses; i++) remain.add(i);
 		for(int[] req : prerequisites){
 			indegree[req[1]]++;
 			List<Integer> next = map.containsKey(req[0]) ? map.get(req[0]): new ArrayList<Integer>();
 			next.add(req[1]);
 			map.put(req[0], next);
 		}
 		Queue<Integer> queue = new LinkedList<>();
 		for(int i = 0; i < numCourses; i++){
 			if(indegree[i] == 0)
 				queue.offer(i);
 		}
 		while(!queue.isEmpty()){
 			int course = queue.poll();
 			remain.remove(course);
 			List<Integer> courses = map.get(course);
 			if(courses == null) continue;
 			for(Integer c : courses){
 				if(--indegree[c] == 0)
 					queue.offer(c);
 			}
 		}
 		return remain.isEmpty();
 	}
 }

Amazon session

Method 1: Topological sort

 class Solution {
 	public boolean canFinish(int numCourses, int[][] prerequisites) {
 		Map<Integer, Set<Integer>> map = new HashMap<>();   //key: current course, value: courses that cur is pre 
 		int[] indegree = new int[numCourses];   // indegree of course
 		for(int[] requests : prerequisites){
 			indegree[requests[0]]++;
 			Set<Integer> req = map.getOrDefault(requests[1], new HashSet<>());
 			req.add(requests[0]);
 			map.put(requests[1], req);
 		}
 		Queue<Integer> q = new LinkedList<>();
 		int finished = 0;
 		for(int i = 0; i < numCourses; i++){
 			if(indegree[i] == 0){
 				q.offer(i);
 			}
 		}
 		while(!q.isEmpty()){
 			int c = q.poll();
 			finished++;
 			if(!map.containsKey(c)) continue;   // current course is not any pre-request for any course.
 			for(int course : map.get(c)){
 				if(--indegree[course] == 0)
 					q.offer(course);
 			}
 		}
 		return finished == numCourses;
 	}
 }

Reference

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