你這個學期必須選修 numCourse 門課程，記為 0 到 numCourse-1 。
在選修某些課程之前需要一些先修課程。 例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們：[0,1]
給定課程總量以及它們的先決條件，請你判斷是否可能完成所有課程的學習？
示例 1:
輸入: 2, [[1,0]]
輸出: true
解釋: 總共有 2 門課程。學習課程 1 之前，你需要完成課程 0。所以這是可能的。
DFS代碼
class Solution {
boolean[] finished;public boolean canFinish(int numCourses, int[][] prerequisites) {finished=new boolean[numCourses];HashMap<Integer,List<Integer>> map=new HashMap<>();//記錄課程學完后可以學習的課程HashMap<Integer,HashSet<Integer>> map2=new HashMap<>();//記錄需要先修的課程for(int i=0;i<numCourses;i++)//創建鄰接表{map.put(i,new ArrayList<>());map2.put(i,new HashSet<>());}for(int[] pre:prerequisites){map.get(pre[1]).add(pre[0]);map2.get(pre[0]).add(pre[1]);}for(int i=0;i<numCourses;i++)Finish(i,map,map2);for(int i=0;i<numCourses;i++)//檢查是不是全部學完了if(!finished[i]) return false;return true;}public void Finish(int cur,HashMap<Integer,List<Integer>> map, HashMap<Integer,HashSet<Integer>> map2) {//深度優先搜索if(!map2.get(cur).isEmpty()) return;finished[cur]=true;for(int next:map.get(cur)){map2.get(next).remove(cur);Finish(next,map,map2);}}
}
BFS代碼
public boolean canFinish(int numCourses, int[][] prerequisites) {Queue<Integer> queue=new LinkedList<>();int[] adj=new int[numCourses];Map<Integer,Set<Integer>> pre=new HashMap<>();for(int i=0;i<numCourses;i++)pre.put(i,new HashSet<>());for(int[] t:prerequisites){pre.get(t[1]).add(t[0]);//鄰接表adj[t[0]]++;//記錄節點的入度}for(int i=0;i<numCourses;i++)//入度為0的節點入隊if(adj[i]==0) queue.add(i);while (!queue.isEmpty()){int cur=queue.poll();for(int c:pre.get(cur))//相鄰節點入度減1{if(--adj[c]==0) queue.offer(c);//入度為0的節點入隊}}for(int i=0;i<numCourses;i++)if(adj[i]>0) return false;//還存在不能消除的邊return true;}
)
