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.
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.
- 思路
修讀課程，給定多組序列[a, b]，表示要學(xué)習(xí)a課程必須先學(xué)習(xí)b課程。問是否可以全部修完n門課程？題目鏈接
拓?fù)渑判蛲章簟＝y(tǒng)計(jì)每個(gè)點(diǎn)（課程）的入度，然后把入度為0的入隊(duì)烹植。再依次出隊(duì)叠纷，每出隊(duì)一次課程數(shù)減一，然后將該點(diǎn)的后續(xù)點(diǎn)入度減一勺择，如果為0則入隊(duì)创南。最后課程數(shù)為0表示可以全部修完。
補(bǔ)充：當(dāng)需要輸出正確的序列時(shí)省核，可以在每次出隊(duì)的時(shí)候記錄該點(diǎn)稿辙，最后判斷是否能修完，若能的話返回結(jié)果
import java.util.LinkedList;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 統(tǒng)計(jì)所有點(diǎn)的入度
int[] inDegrees = new int[numCourses];
for(int[] arr : prerequisites){
inDegrees[arr[0]] ++;
}
// 將入度為0的點(diǎn)加入隊(duì)列
LinkedList<Integer> queue = new LinkedList<Integer>();
for(int i=0; i<numCourses; i++){
if(inDegrees[i] == 0){
queue.add(i);
}
}
// 依次出隊(duì)消除關(guān)系
while( !queue.isEmpty()){
int pre = queue.poll();
numCourses --; // 注意每出隊(duì)一次節(jié)點(diǎn)數(shù)減1
for(int[] arr : prerequisites){
if(arr[1] != pre){ // 當(dāng)起點(diǎn)不是pre時(shí)跳過
continue;
}
if(--inDegrees[arr[0]] == 0){ // 入度減1然后判斷是否可以入隊(duì)
queue.add(arr[0]);
}
}
}
return numCourses == 0;
}
}
