現(xiàn)在你總共有 n 門課需要選壕探，記為 0 到 n - 1.
一些課程在修之前需要先修另外的一些課程博肋，比如要學(xué)習(xí)課程 0 你需要先學(xué)習(xí)課程 1 仓犬，表示為[0,1]
- 給定n門課以及他們的先決條件渗饮，判斷是否可能完成所有課程蚕冬？
在線評測地址：lintcode領(lǐng)扣
例1:
輸入: n = 2, prerequisites = [[1,0]]
輸出: true
例2:
輸入: n = 2, prerequisites = [[1,0],[0,1]]
輸出: false
【題解】
對于兩門課之間的約束關(guān)系傲霸，很容易聯(lián)想到圖疆瑰，我們可以將課抽象為節(jié)點(diǎn)，將約束抽象為一條有向邊昙啄，可以用有向圖的相關(guān)算法解決問題穆役。拓?fù)渑判蛘每梢越鉀Q這一問題。
算法：拓?fù)渑判?/strong>
一個合法的選課序列就是一個拓?fù)湫蚴崃荩負(fù)湫蚴侵敢粋€滿足有向圖上耿币，不存在一條邊出節(jié)點(diǎn)在入節(jié)點(diǎn)后的線性序列，如果有向圖中有環(huán)韧拒，就不存在拓?fù)湫蜓徒印？梢酝ㄟ^拓?fù)渑判蛩惴▉淼玫酵負(fù)湫蚺岩纾约芭袛嗍欠翊嬖诃h(huán)塑悼。
拓?fù)渑判虿襟E：
- 建圖并記錄所有節(jié)點(diǎn)的入度。
- 將所有入度為
0的節(jié)點(diǎn)加入隊列楷掉。 - 取出隊首的元素
now厢蒜，將其加入拓?fù)湫蛄小?/li> - 訪問所有
now的鄰接點(diǎn)nxt，將nxt的入度減1烹植，當(dāng)減到0后斑鸦，將nxt加入隊列。 - 重復(fù)步驟
3草雕、4巷屿，直到隊列為空。 - 如果拓?fù)湫蛄袀€數(shù)等于節(jié)點(diǎn)數(shù)墩虹，代表該有向圖無環(huán)嘱巾，且存在拓?fù)湫颉?/li>
復(fù)雜度分析
設(shè)課程數(shù)憨琳，即圖的節(jié)點(diǎn)數(shù)為V。
約束數(shù)量浓冒，即圖的邊數(shù)為E栽渴。
時間復(fù)雜度O(V + E)
- 建圖，掃描一遍所有的邊
O(E)稳懒。 - 每個節(jié)點(diǎn)最多入隊出隊
1次闲擦，復(fù)雜度O(V)。 - 鄰接表最終會被遍歷
1遍场梆，復(fù)雜度O(E)墅冷。 - 綜上，總復(fù)雜度為
O(E + V)或油。
空間復(fù)雜度O(V + E)
- 鄰接表占用
O(E + V)的空間寞忿。 - 隊列最劣情況寫占用
O(V)的空間。 - 綜上顶岸，總復(fù)雜度為
O(V + E)腔彰。
public class Solution {
/*
* @param numCourses: a total of n courses
* @param prerequisites: a list of prerequisite pairs
* @return: true if can finish all courses or false
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
List[] graph = new ArrayList[numCourses];
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<Integer>();
}
// 建圖
for (int[] edge: prerequisites) {
graph[edge[1]].add(edge[0]);
inDegree[edge[0]]++;
}
int numChoose = 0;
Queue queue = new LinkedList();
// 將入度為 0 的編號加入隊列
for(int i = 0; i < inDegree.length; i++){
if (inDegree[i] == 0) {
queue.add(i);
}
}
while (! queue.isEmpty()) {
int nowPos = (int)queue.poll();
numChoose++;
// 將每條邊刪去，如果入度降為 0辖佣，再加入隊列
for (int i = 0; i < graph[nowPos].size(); i++) {
int nextPos = (int)graph[nowPos].get(i);
inDegree[nextPos]--;
if (inDegree[nextPos] == 0) {
queue.add(nextPos);
}
}
}
return numChoose == numCourses;
}
}
更多題解參見：leetcode/lintcode題解
