Nhận diện bài toán phụ thuộc tiên quyết và hợp đồng chiều mũi tên
Trong thực tế kỹ thuật phần mềm, chúng ta liên tục đối mặt với bài toán giải quyết phụ thuộc (dependency resolution): trình quản lý gói npm/pip cần biết cài thư viện nào trước, hệ thống Makefile/Bazel cần biết biên dịch mô-đun nào trước, hay bảng tính Excel cần biết tính ô công thức nào trước. Trong phỏng vấn thuật toán, mô hình này được đóng gói gọn gàng trong cặp bài toán kinh điển Course Schedule I (kiểm tra có thể học hết n môn không) và Course Schedule II (in ra một thứ tự học hợp lệ).
Đề bài chuẩn cho n môn học đánh số từ 0 đến n - 1 và danh sách các cặp điều kiện tiên quyết [a, b], mang ý nghĩa: muốn học môn a thì bắt buộc phải hoàn thành môn b trước.
Trước khi viết code, bạn hãy làm rõ ngay với người phỏng vấn 4 điểm sau:
- Chiều của cặp
[a, b]trong đầu vào: Trong đề chuẩn LeetCode,[a, b]nghĩa làblà tiên quyết củaa, nên mũi tên luồng học đi từb -> a(học xongbmới mở khóaa). Rất nhiều ứng viên quen tay nối cạnha -> bmà không để ý rằng làm vậy sẽ đảo ngược toàn bộ thứ tự tô-pô! - Đồ thị có thể không liên thông không? Hoàn toàn có thể: các môn đại cương và các môn chuyên ngành có thể tạo thành nhiều cụm độc lập không dính dáng tới nhau, thậm chí có những môn tự chọn không có bất kỳ điều kiện tiên quyết nào (
m = 0). - Danh sách cạnh có thể chứa cặp trùng lặp
[a, b]hoặc tự khuyên[a, a]không? Nếu một môn tự đòi hỏi chính nó làm tiên quyết ([a, a]), bậc vào củaasẽ>= 1và thuật toán phải báo ngay là có chu trình. Nếu có cạnh trùng lặp, ta cần thống nhất hoặc lọc trùng trước, hoặc cộng bậc vào tương ứng với mỗi cạnh trong danh sách kề. - Quy ước đầu ra khi có nhiều thứ tự hợp lệ: Đề bài chấp nhận bất kỳ thứ tự tô-pô nào hay yêu cầu thứ tự từ điển nhỏ nhất (lexicographically smallest)? Nếu yêu cầu thứ tự từ điển nhỏ nhất, ta chỉ cần thay hàng đợi thường
Queuebằng hàng đợi ưu tiênMin-Heap.
Một đồ thị phụ thuộc có hướng tồn tại lịch học hoàn tất toàn bộ n môn khi và chỉ khi nó không có chu trình có hướng (Directed Acyclic Graph — DAG). Với thuật toán Kahn (BFS theo bậc vào), mỗi bước ta chỉ học những môn có số tiên quyết còn thiếu bằng 0 (indeg[u] == 0); nếu khi hàng đợi rỗng mà tổng số môn đã học nhỏ hơn n, chắc chắn phần còn lại đang khóa chặt nhau trong ít nhất một chu trình.
Bất biến bậc vào (In-degree) của thuật toán Kahn
Khi biểu diễn mỗi điều kiện [a, b] thành một cung có hướng b -> a:
- Bậc vào
indeg[a]chính là số lượng môn tiên quyết mà mônavẫn đang chờ được hoàn thành. - Danh sách kề
adj[b]lưu danh sách các môn học phụ thuộc vàob(sẽ được giảm bớt 1 rào cản ngay khi mônbhoàn tất).
Thuật toán Kahn vận hành theo đúng quy trình đăng ký tín chỉ ngoài đời thực:
- Khởi tạo: Quét qua tất cả các môn từ
0đếnn - 1. Mọi môn cóindeg[i] == 0(không đòi hỏi tiên quyết nào) đều có thể học ngay trong học kỳ đầu tiên → đẩy tất cả chúng vào hàng đợi. - Lan truyền tháo gỡ ràng buộc: Lấy một môn
ura khỏi hàng đợi và ghiuvào danh sách kết quảorder. Duyệt qua mọi mônvtrongadj[u]: vìuđã học xong nên rào cản củavgiảm đi 1 (--indeg[v]). Khoảnh khắcindeg[v]vừa chạm mốc0, toàn bộ tiên quyết củavđã được giải quyết xong → đẩyvvào hàng đợi. - Kiểm tra chu trình ở cuối: Khi hàng đợi rỗng, ta kiểm tra
order.size() == n:- Nếu
order.size() == n: toàn bộnmôn đều đã được học, trả vềtrue(cho Course Schedule I) và mảngorder(cho Course Schedule II). - Nếu
order.size() < n: các môn chưa được đưa vàoorderđều cóindeg > 0, nghĩa là chúng đang nằm trong chu trình phụ thuộc vòng tròn (ví dụ0chờ1và1chờ0) hoặc phụ thuộc vào một chu trình như vậy → trả vềfalse/ mảng rỗng.
- Nếu
Chạy tay từng bước trên hai trường hợp: Khả thi và Có chu trình
Trường hợp 1: n = 4 môn, 4 điều kiện [1, 0], [2, 0], [3, 1], [3, 2]
Các cung có hướng là 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3. Mảng bậc vào ban đầu là indeg = [0, 1, 1, 2]. Để kết quả hoàn toàn tất định (ưu tiên môn có chỉ số nhỏ trước khi có nhiều môn cùng sẵn sàng), ta dùng hàng đợi ưu tiên Min-Heap:
| Bước | Hàng đợi trước bước | Môn u lấy ra |
Các môn phụ thuộc v trong adj[u] |
Mảng indeg[0..3] sau khi giảm |
Danh sách order đã học |
|---|---|---|---|---|---|
| Khởi tạo | [0] |
— | — | [0, 1, 1, 2] |
[] |
| 1 | [0] |
u = 0 |
v = 1 (indeg[1]: 1 -> 0, đẩy 1)v = 2 (indeg[2]: 1 -> 0, đẩy 2) |
[0, 0, 0, 2] |
[0] |
| 2 | [1, 2] |
u = 1 |
v = 3 (indeg[3]: 2 -> 1, chưa về 0) |
[0, 0, 0, 1] |
[0, 1] |
| 3 | [2] |
u = 2 |
v = 3 (indeg[3]: 1 -> 0, vừa về 0 → đẩy 3!) |
[0, 0, 0, 0] |
[0, 1, 2] |
| 4 | [3] |
u = 3 |
Không có (adj[3] rỗng) |
[0, 0, 0, 0] |
[0, 1, 2, 3] (Đủ 4 môn!) |
Chú ý ở Bước 2: khi học xong môn 1, môn 3 được giảm indeg[3] từ 2 xuống 1, nhưng vì vẫn còn thiếu môn tiên quyết 2 nên 3 chưa được vào hàng đợi. Phải tới Bước 3 khi môn 2 cũng hoàn thành, indeg[3] mới giảm về 0 và môn 3 mới được mở khóa.
Trường hợp 2: n = 2 môn, 2 điều kiện [1, 0], [0, 1] (Khóa chết vòng tròn)
Các cung là 0 -> 1 và 1 -> 0. Bậc vào ban đầu là indeg = [1, 1]. Ngay ở bước khởi tạo, không có bất kỳ môn nào có indeg == 0, nên hàng đợi rỗng ngay lập tức! Vòng lặp while kết thúc với order.size() = 0 < 2, kết luận ngay đồ thị có chu trình (CYCLE).
Code mẫu C++17, Python và Java 21
Chương trình dưới đây đọc số môn n, số điều kiện m và m cặp a b (môn b là tiên quyết của a). Bằng cách dùng Min-Heap cho hàng đợi của thuật toán Kahn, chương trình in ra thứ tự học hợp lệ có thứ tự từ điển nhỏ nhất, hoặc in ra "CYCLE" nếu không thể hoàn thành đủ n môn.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<vector<int>> adj(n);
vector<int> indeg(n, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
adj[b].push_back(a);
indeg[a]++;
}
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) q.push(i);
}
vector<int> order;
while (!q.empty()) {
int u = q.top();
q.pop();
order.push_back(u);
for (int v : adj[u]) {
if (--indeg[v] == 0) {
q.push(v);
}
}
}
if ((int)order.size() < n) {
cout << "CYCLE\n";
} else {
for (int i = 0; i < n; i++) {
cout << (i ? " " : "") << order[i];
}
cout << '\n';
}
return 0;
}
import heapq
import sys
def main() -> None:
data = list(map(int, sys.stdin.buffer.read().split()))
if len(data) < 2:
return
n, m = data[0], data[1]
adj: list[list[int]] = [[] for _ in range(n)]
indeg = [0] * n
for i in range(m):
a, b = data[2 + 2 * i], data[3 + 2 * i]
adj[b].append(a)
indeg[a] += 1
heap = [i for i in range(n) if indeg[i] == 0]
heapq.heapify(heap)
order: list[int] = []
while heap:
u = heapq.heappop(heap)
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
heapq.heappush(heap, v)
if len(order) < n:
print("CYCLE")
else:
print(" ".join(map(str, order)))
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) return;
int n = sc.nextInt();
int m = sc.nextInt();
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
adj.get(b).add(a);
indeg[a]++;
}
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) pq.offer(i);
}
List<Integer> order = new ArrayList<>();
while (!pq.isEmpty()) {
int u = pq.poll();
order.add(u);
for (int v : adj.get(u)) {
if (--indeg[v] == 0) {
pq.offer(v);
}
}
}
if (order.size() < n) {
System.out.println("CYCLE");
} else {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
if (i > 0) sb.append(' ');
sb.append(order.get(i));
}
System.out.println(sb);
}
}
}
Lưu ý trong phỏng vấn: Nếu đề bài chỉ yêu cầu một thứ tự hợp lệ bất kỳ (không cần thứ tự từ điển nhỏ nhất), bạn hãy thay priority_queue bằng std::queue<int> (C++), collections.deque (Python) hoặc ArrayDeque<Integer> (Java) để mỗi thao tác đẩy/lấy chỉ tốn O(1) thay vì O(log V).
Độ phức tạp và so sánh Kahn BFS với DFS 3 màu
- Thời gian:
- Dùng hàng đợi thường (
Queue/deque):O(V + E)với \(V = n\) là số môn học và \(E = m\) là số điều kiện tiên quyết, vì mỗi đỉnh chỉ vào/ra hàng đợi tối đa 1 lần và mỗi cungu -> vchỉ được duyệt đúng 1 lần khiurời hàng đợi. - Dùng hàng đợi ưu tiên (
Min-Heapđể lấy thứ tự từ điển nhỏ nhất):O(V log V + E).
- Dùng hàng đợi thường (
- Bộ nhớ phụ:
O(V + E)để lưu danh sách kềadj, mảng bậc vàoindegvà hàng đợi.
Trong phỏng vấn, người phỏng vấn có thể hỏi thêm: "Ngoài cách dùng bậc vào Kahn, em có biết cách dùng DFS để vừa tìm chu trình vừa lấy thứ tự tô-pô không?" Bạn hãy nắm vững bảng so sánh hai trường phái dưới đây:
| Tiêu chí | Thuật toán Kahn (BFS + Bậc vào indeg) |
DFS 3 màu (Trạng thái 0, 1, 2 + Hậu thứ tự) |
|---|---|---|
| Cách phát hiện chu trình | Cuối thuật toán kiểm tra số đỉnh lấy ra < V |
Trong lúc DFS từ u, nếu chạm phải đỉnh kề v đang có color[v] == 1 (đang nằm trên đường đi đệ quy hiện tại — cung ngược back-edge) thì báo có chu trình |
| Cách lấy thứ tự tô-pô | Thứ tự lấy các đỉnh ra khỏi hàng đợi chính là thứ tự tô-pô thuận | Đẩy đỉnh u vào mảng sau khi đã thăm hết các con (color[u] = 2), cuối cùng phải đảo ngược (reverse) mảng kết quả |
| Độ an toàn ngăn xếp | Rất an toàn vì dùng hàng đợi trên Heap | Có nguy cơ tràn ngăn xếp đệ quy (Stack Overflow) nếu đồ thị là một chuỗi dài \(10^5\) đỉnh |
| Mở rộng quy hoạch động trên DAG | Cực kỳ tự nhiên: truyền giá trị DP thuận chiều từ u sang v ngay khi giảm --indeg[v] |
Tự nhiên khi tính DP từ đích lùi về nguồn (ghi nhớ hóa đệ quy Memoization) |
Các bài toán phỏng vấn nâng cao dùng chung khung Course Schedule
Một khi đã viết thành thạo khung Kahn BFS, bạn có thể giải quyết ngay hàng loạt bài toán đồ thị mức độ Medium - Hard trong Big Tech:
- Alien Dictionary (Từ điển người ngoài hành tinh — LeetCode 269): Cho danh sách các từ đã sắp xếp theo bảng chữ cái lạ, hãy suy ra thứ tự các chữ cái. Cách giải: So sánh từng cặp từ đứng kề nhau
w1, w2, tìm vị trí đầu tiên hai ký tự khác nhauc1 != c2để tạo một cung tiên quyếtc1 -> c2, sau đó chạy đúng thuật toán Kahn! (Đừng quên bẫy đặc biệt: nếuw1dài hơnw2màw2lại là tiền tố củaw1như"abc"đứng trước"ab", trả về ngay không hợp lệ). - Parallel Courses / Minimum Semesters (Số học kỳ tối thiểu): Nếu một học kỳ bạn được học không giới hạn số môn miễn là đã đủ tiên quyết, hỏi cần ít nhất bao nhiêu học kỳ? Cách giải: Kết hợp thuật toán Kahn với kỹ thuật tách tầng
sz = q.size()! Mỗi tầng BFS tương ứng với đúng 1 học kỳ. - Find Eventual Safe States (Tìm các đỉnh an toàn): Một đỉnh là an toàn nếu mọi đường đi bắt đầu từ nó đều dẫn tới đỉnh kết thúc (không đi vào chu trình). Cách giải: Đảo ngược chiều tất cả các cung trên đồ thị rồi chạy thuật toán Kahn từ các đỉnh có bậc ra ban đầu bằng
0; mọi đỉnh được lấy ra khỏi hàng đợi đều là đỉnh an toàn.
Những lỗi sai phổ biến và cách tự kiểm tra code
- Dùng mảng
bool visitedđơn thuần (2 trạng thái) để tìm chu trình trên đồ thị có hướng bằng DFS: Đây là lỗi sai nghiêm trọng nhất khi dùng DFS! Trên đồ thị có hướng, nếu từ gốc0có hai nhánh0 -> 1 -> 3và0 -> 2 -> 3, khi nhánh thứ nhất thăm xong3và quay lui, nếu bạn chỉ đánh dấuvisited[3] = truerồi khi đi nhánh thứ hai0 -> 2 -> 3thấyvisited[3]đãtruemà kết luận có chu trình thì hoàn toàn sai (đó chỉ là cung chéo hội tụ cross-edge, không phải chu trình). Với DFS trên đồ thị có hướng, bắt buộc phải dùng 3 màu:0(chưa thăm),1(đang trên ngăn xếp đường đi hiện tại),2(đã thăm xong hoàn toàn). - Đẩy đỉnh vào hàng đợi khi
--indeg[v]thay vì khi--indeg[v] == 0: Nếu một môn có 2 tiên quyết, lần giảm đầu tiên mới đưaindeg[v]từ2xuống1. Chỉ khi nàoindeg[v]chạm đúng0thì mới được đẩy vào hàng đợi. - Quên kiểm tra
order.size() < ntrước khi trả về mảngordertrong Course Schedule II: Nếu đồ thị có một nhánh rời không chu trình và một cụm có chu trình, hàng đợi vẫn lấy ra được vài môn ở nhánh rời rồi mới dừng. Nếu không kiểm traorder.size() == n, bạn sẽ trả về một danh sách thiếu môn thay vì trả về mảng rỗng[]theo yêu cầu đề bài.
Để tự kiểm tra code, bạn hãy chạy đối chiếu trên 3 ca biên:
- Đồ thị kim cương hội tụ
0 -> {1, 2} -> 3(4môn,4cạnh → không phải chu trình, thứ tự0 1 2 3). - Đồ thị 2 đỉnh khóa chéo
0 <-> 1→ in raCYCLE. - Đồ thị rời rạc hoàn toàn không có cạnh nào (
n = 3, m = 0→ cả 3 môn đều cóindeg = 0ngay từ đầu, in ra0 1 2).
Luyện ngay trên Big-O Coding
Bạn hãy thực hành ngay chuỗi bài toán Course Schedule I, Course Schedule II và sắp xếp tô-pô trong lộ trình Coding Interview 150 dưới đây.
Câu hỏi thường gặp
Tại sao khi phát hiện chu trình trên đồ thị vô hướng chỉ cần mảng visited 2 trạng thái (kèm đỉnh cha), còn đồ thị có hướng lại cần DFS 3 trạng thái hoặc thuật toán Kahn?
Trên đồ thị vô hướng, mọi cạnh đều đi được cả hai chiều u - v, nên bất kỳ khi nào bạn gặp lại một đỉnh đã thăm v != parent thì luôn khép kín thành một vòng lặp. Ngược lại, trên đồ thị có hướng, các cạnh là đường một chiều: việc hai đường đi khác nhau cùng đổ về một đỉnh đích 3 (0 -> 1 -> 3 và 0 -> 2 -> 3) không tạo thành vòng lặp quay về 0. Chỉ khi gặp lại một đỉnh vẫn đang nằm trên chuỗi tổ tiên chưa thoát đệ quy (color == 1) thì mới có đường một chiều quay ngược lại tạo thành chu trình.
Làm sao đếm được có tất cả bao nhiêu thứ tự tô-pô hợp lệ?
Bài toán đếm tổng số thứ tự tô-pô của một DAG tổng quát thuộc lớp #P-complete (rất nặng về tính toán). Nếu số môn nhỏ (\(n \le 16\)), người ta dùng Quy hoạch động trạng thái Bitmask (dp[mask]) với thời gian \(O(n \cdot 2^n)\); còn trong phỏng vấn chuẩn với \(n \le 2000\), đề bài chỉ yêu cầu kiểm tra tồn tại hoặc trả về một thứ tự hợp lệ bất kỳ trong \(O(V + E)\).
Nếu có cạnh trùng lặp trong danh sách điều kiện tiên quyết thì thuật toán Kahn có bị sai không?
Thuật toán Kahn trong bài viết hoàn toàn không bị ảnh hưởng bởi cạnh trùng lặp! Lý do là mỗi lần đọc một cạnh trùng b -> a, ta vừa thêm a vào adj[b] một lần nữa, vừa cộng indeg[a] thêm 1. Khi b được lấy ra khỏi hàng đợi, vòng lặp duyệt qua adj[b] cũng sẽ gặp a đúng bấy nhiêu lần và trừ đi đúng số lượng đã cộng thêm, nên indeg[a] vẫn về 0 chính xác.
Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

