你這個(gè)學(xué)期必須選修 numCourses 門課程，記為?0?到?numCourses - 1 。
在選修某些課程之前需要一些先修課程。 先修課程按數(shù)組?prerequisites 給出，其中?prerequisites[i] = [ai, bi] ，表示如果要學(xué)習(xí)課程?ai 則 必須 先學(xué)習(xí)課程? bi 。
例如，先修課程對(duì)?[0, 1] 表示：想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 。
請(qǐng)你判斷是否可能完成所有課程的學(xué)習(xí)？如果可以，返回 true ；否則，返回 false 。
示例 1：
????????????輸入：numCourses = 2, prerequisites = [[1,0]]
????????????輸出：true
????????????解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要完成課程 0 。這是可能的。
示例 2：
????????????輸入：numCourses = 2, prerequisites = [[1,0],[0,1]]
????????????輸出：false
????????????解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要先完成課程 0 ；并且學(xué)習(xí)課程 0 之前，你還應(yīng)先完成課程 1 。這是不可能的。
解題思路：拓?fù)渑判?，這個(gè)問題等價(jià)于求有向圖中是否存在循環(huán)。如果存在一個(gè)循環(huán)，則不存在拓?fù)湫蛄?，因此不可能修完所有課程。
拓?fù)渑判蚍椒ǎ?.在有向圖中任意選一個(gè)沒有前驅(qū)的節(jié)點(diǎn)，（且輸出）；
? ? ? ? ? ? ? ? ? ? ? ? ?2.從圖中刪除該頂點(diǎn) 以及 所有以它為尾的邊；
? ? ? ? ? ? ? ? ? ? ? ? ?3.重復(fù)12， 直至全部節(jié)點(diǎn)均已輸出，或圖中不存在無前驅(qū)的頂點(diǎn)為止。?
判斷圖節(jié)點(diǎn)是否有先驅(qū)節(jié)點(diǎn)，利用圖節(jié)點(diǎn)的入度來計(jì)算，如果一個(gè)節(jié)點(diǎn)入度==0，則該節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)。
public?boolean?canFinish(int?numCourses,?int[][]?prerequisites)?{
? ??????// 1.根據(jù)邊的關(guān)系來構(gòu)造圖
? ? ? ? List<Integer>[]?graph?=?new?List[numCourses];?//構(gòu)造鄰接表來存儲(chǔ)圖
????????for?(int?i=0;?i<numCourses;?i++)?{
????????????graph[i]?=?new?ArrayList<>();
????????}?
????????for(int[]?pre?:?prerequisites)?{
????????????graph[pre[1]].add(pre[0]);
????????}
? ??????// 2.創(chuàng)建入度表
????????int[]?inDegree?=?new?int[numCourses];
????????for?(int?i=0;?i<numCourses;?i++)?{
????????????List<Integer>?per?=?graph[i];
????????????for?(int?j?:?per)?{
????????????????inDegree[j]?+=?1;
????????????}
????????}
? ??????// 3.入度為0的節(jié)點(diǎn)入隊(duì)列，然后刪除這個(gè)節(jié)點(diǎn) 以及所有關(guān)系（?對(duì)應(yīng)的節(jié)點(diǎn)的入度-1）
????????Queue<Integer>?queue?=?new?LinkedList<>();
????????for?(int?i=0;?i<numCourses;?i++)?{
????????????if(inDegree[i]?==?0){
????????????????queue.offer(i);
????????????}
????????}
????????while(!queue.isEmpty())?{
????????????int?temp?=?queue.poll();
????????????numCourses--; //刪除temp節(jié)點(diǎn)后，節(jié)點(diǎn)總數(shù)-1
????????????for?(int?next?:?graph[temp])?{
????????????????inDegree[next]?-=?1; //對(duì)應(yīng)的節(jié)點(diǎn)的入度-1
????????????????if(inDegree[next]?==?0)?{
????????????????????queue.offer(next);
????????????????}
????????????}
????????}
????????return?numCourses?==?0; //判斷是否把所有節(jié)點(diǎn)都刪除了，是則代表無循環(huán)圖，返回true
????}
