拓撲排序 — 實戰題解
章節優先度優先度 5／5 — 必備 — 幾乎每一輪面試都會出現必備優先度 4／5 — 高價值 — 這裡有缺口就會掉關高價值優先度 3／5 — 值得會 — 多半是必備模式的變形值得會優先度 2／5 — 冷門 — 讀過一次即可，除非目標公司已知會問冷門只標在真正需要的章節上 —— 沒標的是背景／參考資料。
範圍 — topology_sorting.md 背後的題目集：每題一張 problem card，依照它歸約到的模板分組，本身不放任何模板或理論。 另見：topology_sorting.md — 這些卡片套用的十個模板、題型分類與決策流程；graph.md — LC 207 和 LC 802 在那裡是 Kahn 與三態 DFS 兩張卡的錨定題；bfs.md 和 dfs.md — Kahn 演算法與三色模板所依靠的兩種走訪。
LeetCode 題目清單
總覽
經典的依賴順序題，每題一張 problem card，放在它歸約到的 topology_sorting.md 模板底下。排序本身幾乎從來不是難處， 難處是決定節點和邊是什麼：課程、字母、序列裡的數字、樹的葉子。topology_sorting.md 放模板；這份放題目。
索引
| LC | 題目 | 歸約到 | 難度 |
|---|---|---|---|
| 210 | Course Schedule II | Template 1 — Kahn 演算法，回傳順序 | Medium |
| 444 | Sequence Reconstruction | Template 1 — Kahn 演算法，佇列永遠不會同時有兩個 | Medium |
| 269 | Alien Dictionary | Template 1 — 對相鄰單字讀出的邊跑 Kahn | Hard |
| 1136 | Parallel Courses | Template 6 — Kahn 的一層 = 一個學期 | Medium |
| 310 | Minimum Height Trees | Template 7 — 剝葉子 | Medium |
在別份解過 — 一題一個家，所以這些只是指標：
| LC | 題目 | 解在 |
|---|---|---|
| 207 | Course Schedule | graph.md § Template 4 |
| 802 | Find Eventual Safe States | graph.md § Template 5 |
| 547 | Number of Provinces | graph.md § Template 1（走訪）；union_find_examples.md（union-find） |
| 329 | Longest Increasing Path in a Matrix | topology_sorting.md § Template 9 |
Kahn 演算法範例
Course Schedule II — LC 210 優先度 5／5 — 必備 — 幾乎每一輪面試都會出現
關鍵 — 一門課只有在它所有先修課都已經彈出之後才會彈出，所以彈出的順序就是合法的課表。 環會讓其中的課入度永遠大於 0，所以順序會變短：
len(order) < numCourses代表排不出課表。
歸約到：Template 1 — 回傳順序而不是是／否的 Kahn 演算法（只問是／否的是 LC 207，見 graph.md § Template 4）。
python
# python
# LC 210 - Course Schedule II
# IDEA: Kahn's — pop courses whose prerequisites are all taken; a short order means a cycle
# time = O(V + E), space = O(V + E)
from collections import defaultdict, deque
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, pre in prerequisites:
graph[pre].append(course) # pre must come before course
in_degree[course] += 1
queue = deque(c for c in range(numCourses) if in_degree[c] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node) # every prerequisite of node is already in order
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
# findOrder(4, [[1,0],[2,0],[3,1],[3,2]]) -> [0, 1, 2, 3]
# findOrder(2, [[1,0],[0,1]]) -> []
java
// java
// LC 210 - Course Schedule II
// IDEA: Kahn's — pop courses whose prerequisites are all taken; a short order means a cycle
// time = O(V + E), space = O(V + E)
import java.util.*;
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
int[] inDegree = new int[numCourses];
for (int[] p : prerequisites) {
graph.get(p[1]).add(p[0]); // p[1] must come before p[0]
inDegree[p[0]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int[] order = new int[numCourses];
int size = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
order[size++] = node;
for (int next : graph.get(node)) {
if (--inDegree[next] == 0) {
queue.offer(next);
}
}
}
return size == numCourses ? order : new int[0];
}
}
陷阱
[a, b]的意思是 b 在 a 之前：邊是b → a。方向弄反會回傳反過來的順序，它照樣通過環檢查， 卻會讓每個順序測試失敗。- 沒有先修、也沒人依賴它的課仍然是節點：佇列要從
range(numCourses)播種，不要從graph的 key。 - DFS 的替代做法（沿
course → prerequisite邊做後序）也行。它的三態環檢查見 graph.md § Template 5。
Sequence Reconstruction — LC 444
關鍵 —
nums是唯一最短超序列，恰好等於拓撲順序唯一；而順序唯一，恰好等於 Kahn 的佇列 從來不會同時有超過一個節點。兩個節點同時就緒，就代表有兩種合法順序。
歸約到：Template 1 — Kahn 演算法，外加檢查佇列是否唯一，並在每次彈出時和 nums 比對。
python
# python
# LC 444 - Sequence Reconstruction
# IDEA: edges from each adjacent pair; run Kahn's; fail if the queue ever holds 2 or the pop order leaves nums
# time = O(n + total sequence length), space = O(n + edges)
from collections import defaultdict, deque
def sequenceReconstruction(nums, sequences):
n = len(nums)
graph = defaultdict(set)
in_degree = [0] * (n + 1) # values are 1..n
for seq in sequences:
for a, b in zip(seq, seq[1:]):
if b not in graph[a]: # a duplicate edge must not count twice
graph[a].add(b)
in_degree[b] += 1
queue = deque(v for v in range(1, n + 1) if in_degree[v] == 0)
index = 0
while queue:
if len(queue) > 1:
return False # two candidates for the next slot: not unique
node = queue.popleft()
if node != nums[index]:
return False
index += 1
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return index == n
# sequenceReconstruction([1,2,3], [[1,2],[1,3]]) -> False (2 and 3 can swap)
# sequenceReconstruction([1,2,3], [[1,2],[1,3],[2,3]]) -> True
陷阱
- 同一條邊只算一次。否則
[[1,2],[1,2]]會把in_degree[2]加到 2，2 永遠不會被釋放。 - 沒有出現在任何序列裡的值，一開始入度就是 0，所以它會和真正的第一個元素同時在佇列裡，檢查就失敗。 這正是對的答案：沒有任何資訊固定它的位置。
Alien Dictionary — LC 269 優先度 4／5 — 高價值 — 這裡有缺口就會掉關
關鍵 — 一對相鄰單字唯一提供的順序資訊，在它們第一個不同的字母。後面的字母什麼都沒說。 每對相鄰單字讀出一條邊，再對字母做拓撲排序。唯一沒有任何順序能解釋的輸入，是某個單字後面接著它自己的 真前綴（
"abc"在"ab"之前）。
歸約到：Template 1 — 先從單字列表建圖，再跑 Kahn 演算法。
python
# python
# LC 269 - Alien Dictionary
# IDEA: one edge per adjacent word pair (first differing letter); Kahn's over all letters; short order = cycle
# time = O(C), space = O(1) C = total letters; the graph has at most 26 nodes
from collections import deque
def alienOrder(words):
graph = {c: set() for word in words for c in word} # every letter is a node, even with no edge
in_degree = {c: 0 for c in graph}
for first, second in zip(words, words[1:]):
for a, b in zip(first, second):
if a != b: # the first difference is the only fact this pair gives
if b not in graph[a]:
graph[a].add(b)
in_degree[b] += 1
break
else:
if len(first) > len(second): # "abc" before "ab": no order can explain it
return ""
queue = deque(c for c in in_degree if in_degree[c] == 0)
order = []
while queue:
c = queue.popleft()
order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return "".join(order) if len(order) == len(graph) else ""
# alienOrder(["wrt","wrf","er","ett","rftt"]) -> "wertf"
# alienOrder(["z","x","z"]) -> "" (z < x < z is a cycle)
陷阱
- 在第一個不同的字母就停（
break）。比較每個位置會加進假的邊。 - 前綴的情況只有在迴圈沒有找到差異時才偵測得到；這就是
for … else的用途。["abc", "ab"]必須回傳""。 - 沒出現在任何邊裡的字母仍然屬於答案：讀邊之前，先為每個單字的每個字母建立節點。
平行任務排程範例
Parallel Courses — LC 1136
關鍵 — 每學期把所有能修的課都修掉是最佳的，所以 Kahn BFS 的一層就是一個學期，答案就是層數， 也就是 DAG 裡最長的鏈。環會讓某些課修不到：回傳 −1。
歸約到：Template 6 — 逐層的 Kahn 演算法，每個任務都花一單位時間。
python
# python
# LC 1136 - Parallel Courses
# IDEA: Kahn's by levels; each level is one semester; fewer than n taken means a cycle
# time = O(V + E), space = O(V + E)
from collections import defaultdict, deque
def minimumSemesters(n, relations):
graph = defaultdict(list)
in_degree = [0] * (n + 1) # courses are 1..n
for pre, course in relations:
graph[pre].append(course)
in_degree[course] += 1
queue = deque(c for c in range(1, n + 1) if in_degree[c] == 0)
semesters = 0
taken = 0
while queue:
semesters += 1 # one BFS level = one semester
for _ in range(len(queue)):
course = queue.popleft()
taken += 1
for nxt in graph[course]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt) # unlocked now, taken next semester
return semesters if taken == n else -1
# minimumSemesters(3, [[1,3],[2,3]]) -> 2
# minimumSemesters(3, [[1,2],[2,3],[3,1]]) -> -1
陷阱
- 進入每層迴圈前先凍結
len(queue)。學期中解鎖的課會加到同一個 deque，必須等下一學期。 - 若每學期最多只能修
k門（LC 1494），逐層 greedy 就不再最佳；那題是 bitmask DP。
剝葉子範例
Minimum Height Trees — LC 310 優先度 4／5 — 高價值 — 這裡有缺口就會掉關
關鍵 — 高度最小的根，是樹上最長路徑的中心，所以一層一層剝掉葉子，直到剩下最多兩個節點。 一條路徑的中心有一個或兩個，所以答案永遠是一個或兩個節點。每個節點只被剝一次，所以是 O(n)； 從每個節點各跑一次 BFS 則是 O(n²)。
歸約到：Template 7 — 在無向樹上做 Kahn 式的剝除，以「度數為 1」作為就緒條件。
python
# python
# LC 310 - Minimum Height Trees
# IDEA: peel all current leaves (degree 1) per round until <= 2 nodes remain; the survivors are the centres
# time = O(n), space = O(n)
from collections import deque
def findMinHeightTrees(n, edges):
if n == 1:
return [0] # no edges, so no leaf of degree 1
graph = [[] for _ in range(n)]
degree = [0] * n
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
degree[u] += 1
degree[v] += 1
leaves = deque(i for i in range(n) if degree[i] == 1)
remaining = n
while remaining > 2:
remaining -= len(leaves) # peel one whole layer
for _ in range(len(leaves)):
leaf = leaves.popleft()
for nxt in graph[leaf]:
degree[nxt] -= 1
if degree[nxt] == 1: # nxt is a leaf of the trimmed tree
leaves.append(nxt)
return list(leaves)
# findMinHeightTrees(4, [[1,0],[1,2],[1,3]]) -> [1]
# findMinHeightTrees(6, [[3,0],[3,1],[3,2],[3,4],[5,4]]) -> [3, 4]
java
// java
// LC 310 - Minimum Height Trees
// IDEA: peel all current leaves (degree 1) per round until <= 2 nodes remain; the survivors are the centres
// time = O(n), space = O(n)
import java.util.*;
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) {
return Collections.singletonList(0);
}
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
int[] degree = new int[n];
for (int[] e : edges) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]);
degree[e[0]]++;
degree[e[1]]++;
}
Deque<Integer> leaves = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (degree[i] == 1) {
leaves.offer(i);
}
}
int remaining = n;
while (remaining > 2) {
int layer = leaves.size();
remaining -= layer;
for (int i = 0; i < layer; i++) {
int leaf = leaves.poll();
for (int next : graph.get(leaf)) {
if (--degree[next] == 1) {
leaves.offer(next);
}
}
}
}
return new ArrayList<>(leaves);
}
}
陷阱
n == 1沒有邊，也沒有度數為 1 的節點；少了這個防護，答案會是[]。- 停在
remaining > 2，不是「佇列空了」。剝過兩個節點就把中心刪掉了。 - 每輪剝掉一整層（凍結大小）。一次剝一片葉子，可能讓樹的一側比另一側剝得快，最後停在偏離中心的地方。
相似題 — LC 2603（先剝掉沒有硬幣的葉子）· LC 1245（樹的直徑：它的中點就是中心）