題目
題目描述
現(xiàn)在你總共有 n 門課需要選，記為 0 到 n-1珍特。
在選修某些課程之前需要一些先修課程旨椒。 例如晓褪，想要學習課程 0 ，你需要先完成課程 1 综慎，我們用一個匹配來表示他們: [0,1]
給定課程總量以及它們的先決條件涣仿，判斷是否可能完成所有課程的學習？
示例 1:
輸入: 2, [[1,0]]
輸出: true
解釋: 總共有 2 門課程示惊。學習課程 1 之前好港，你需要完成課程 0。所以這是可能的涝涤。
示例 2:
輸入: 2, [[1,0],[0,1]]
輸出: false
解釋: 總共有 2 門課程媚狰。學習課程 1 之前，你需要先完成?課程 0阔拳；并且學習課程 0 之前崭孤，你還應先完成課程 1。這是不可能的糊肠。
說明:
輸入的先決條件是由邊緣列表表示的圖形辨宠，而不是鄰接矩陣。詳情請參見圖的表示法货裹。
你可以假定輸入的先決條件中沒有重復的邊嗤形。
提示:
這個問題相當于查找一個循環(huán)是否存在于有向圖中。如果存在循環(huán)弧圆，則不存在拓撲排序赋兵，因此不可能選取所有課程進行學習笔咽。
通過 DFS 進行拓撲排序
- 一個關(guān)于Coursera的精彩視頻教程（21分鐘），介紹拓撲排序的基本概念霹期。
拓撲排序也可以通過 BFS 完成叶组。
題解
簡單拓撲排序應用
代碼
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> v = new HashMap<>();
int[] at = new int[numCourses];
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < prerequisites.length; i++) {
if (!v.containsKey(prerequisites[i][0])) {
v.put(prerequisites[i][0], new ArrayList<Integer>());
}
v.get(prerequisites[i][0]).add(prerequisites[i][1]);
at[prerequisites[i][1]]++;
}
for (int i = 0; i < numCourses; i++) {
if (at[i] == 0) {
q.add(i);
}
}
int count = 0;
while (!q.isEmpty()) {
int num = q.poll();
count++;
if (v.containsKey(num)) {
for (int i = 0; i < v.get(num).size(); i++) {
at[v.get(num).get(i)]--;
if (at[v.get(num).get(i)] == 0) {
q.add(v.get(num).get(i));
}
}
}
}
return count == numCourses;
}
結(jié)果
image.png
