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?
For example:
2, [[1,0]]There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]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.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.You may assume that there are no duplicate edges in the input prerequisites.
click to show more hints.
package com.graph; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class M207_Course_Schedule { int n; int[][] pre; int[] visited; int m; //方法一：根据图的DFS策略，如果遍历过程中发现环，则不能修完所有课 //递归 //TC=O(m^n) public boolean canFinish_rec(int numCourses, int[][] prerequisites) { n = numCourses; pre = prerequisites; if(n==0 || n==1) return true; if(pre==null || pre.length<1) return true; visited = new int[n]; m = pre.length; boolean flag = true; for(int i=0; i<n; i++) { if(visited[i]==0) { visited[i] = 1; flag = DFS(i); visited[i] = 2; if(!flag) return false; } } return flag; } boolean DFS(int v) { boolean flag = true; for(int i=0; i<m; i++) {//遍历边的时候，可以优化，将已经访问过的边标记 int a = pre[i][0]; int b = pre[i][1]; if(b==v) { //到这里，说明b是访问过的 if(visited[a]==0) { visited[a]=1; flag = DFS(a); visited[a]=2; if(!flag) return false; }else if(visited[a]==1) return false; } } return flag; } //迭代 //TC=O(m^n) public boolean canFinish_it(int numCourses, int[][] prerequisites) { n = numCourses; pre = prerequisites; if(n==0 || n==1) return true; if(pre==null || pre.length<1) return true; visited = new int[n]; m = pre.length; Stack<Integer> stack = new Stack<Integer>(); for(int i=0; i<n; i++) { if(visited[i]==0) { stack.push(i); visited[i] = 1; } int v; while(!stack.isEmpty()) { v = stack.peek();//revise int j=0; int flag=0; for(; j<m; j++) {//遍历边的时候，可以优化，将已经访问过的边标记 int a = pre[j][0]; int b = pre[j][1]; if(v==b) { if(visited[a]==0) { flag=1; stack.push(a); visited[a]=1; break; }else if(visited[a]==1) return false; } } //revise if(flag==0) { v = stack.pop(); visited[v] = 2; } } } return true; } //方法二：根据拓扑排序，实质为BFS策略 public boolean canFinish_1(int numCourses, int[][] prerequisites) { //空间换时间 n = numCourses; pre = prerequisites; m = pre.length; int[] nums = new int[n]; for(int i=0; i<m; i++) { nums[pre[i][1]]++; } Queue<Integer> q = new LinkedList<Integer>(); int count=0; for(int i=0; i<n; i++) { if(nums[i]==0) { q.add(i); count++; } } while(!q.isEmpty()) { int t = q.poll(); for(int i=0; i<m; i++) { if(t==pre[i][0]) { int k = pre[i][1]; nums[k]--; if(nums[k]==0) { q.add(k); count++; } } } } return count==n; } public static void main(String[] args) { M207_Course_Schedule m = new M207_Course_Schedule(); m.canFinish_it(3, new int[][] {{1,0},{2,0},{0,2}}); } }
