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