Phỏng vấn

Bài toán lịch học (Course Schedule) và sắp xếp tô-pô

Mọi bài toán lập lịch công việc, biên dịch gói phần mềm hay đăng ký môn học có điều kiện tiên quyết đều quy về đồ thị có hướng không chu trình (DAG). Thuật toán Kahn dựa trên bậc vào (in-degree) giúp bạn đồng thời kiểm tra tính khả thi (Course Schedule I) và trích xuất thứ tự học hợp lệ (Course Schedule II) trong O(V + E).

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:

  1. Chiều của cặp [a, b] trong đầu vào: Trong đề chuẩn LeetCode, [a, b] nghĩa là b là tiên quyết của a, nên mũi tên luồng học đi từ b -> a (học xong b mới mở khóa a). Rất nhiều ứng viên quen tay nối cạnh a -> b mà không để ý rằng làm vậy sẽ đảo ngược toàn bộ thứ tự tô-pô!
  2. Đồ 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).
  3. 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ủa a sẽ >= 1 và 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ề.
  4. 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 Queue bằng hàng đợi ưu tiên Min-Heap.
Ý chính

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.

Course Schedule (Kahn Topo Sort): Đồ thị kim cương 4 môn học Môn 0 indeg=0 Môn 1 indeg=1 Môn 2 indeg=1 Môn 3 indeg=2 Lớp 1: pop(0) indeg[1]=0, indeg[2]=0 Lớp 2: pop(1), pop(2) indeg[3] giảm 2 → 1 → 0 Lớp 3: pop(3) → đủ 4 môn Thứ tự: 0 → 1 → 2 → 3 Nếu số đỉnh lấy ra < n thì đồ thị có chu trình (CYCLE) · O(V + E)
Course Schedule: 0 → (1, 2) → 3 Bán bậc vào ban đầu: indeg = [0, 1, 1, 2] Bước 1: lấy Môn 0 (indeg = 0) Giảm indeg[1] và indeg[2] về 0 Bước 2: lấy Môn 1 và Môn 2 Giảm indeg[3] từ 2 → 1 → 0 Bước 3: lấy Môn 3 (indeg = 0) Đủ 4/4 môn → Thứ tự: [0, 1, 2, 3] Thuật toán Kahn (BFS) · O(V + E)
Hình 1. Thuật toán Kahn trên 4 môn học với điều kiện 0 -> {1, 2} -> 3: bắt đầu từ môn 0 có bậc vào bằng 0, lần lượt tháo gỡ tiên quyết cho môn 1, môn 2 rồi môn 3 để thu được thứ tự hợp lệ 0 -> 1 -> 2 -> 3.

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ôn a vẫ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ào b (sẽ được giảm bớt 1 rào cản ngay khi môn b hoà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:

  1. Khởi tạo: Quét qua tất cả các môn từ 0 đến n - 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.
  2. Lan truyền tháo gỡ ràng buộc: Lấy một môn u ra khỏi hàng đợi và ghi u vào danh sách kết quả order. Duyệt qua mọi môn v trong adj[u]: vì u đã học xong nên rào cản của v giảm đi 1 (--indeg[v]). Khoảnh khắc indeg[v] vừa chạm mốc 0, toàn bộ tiên quyết của v đã được giải quyết xong → đẩy v vào hàng đợi.
  3. 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ộ n môn đều đã được học, trả về true (cho Course Schedule I) và mảng order (cho Course Schedule II).
    • Nếu order.size() < n: các môn chưa được đưa vào order đề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ụ 0 chờ 1 và 1 chờ 0) hoặc phụ thuộc vào một chu trình như vậy → trả về false / mảng rỗng.

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;
}

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 cung u -> v chỉ được duyệt đúng 1 lần khi u rờ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).
  • Bộ nhớ phụ: O(V + E) để lưu danh sách kề adj, mảng bậc vào indeg và 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:

  1. 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 nhau c1 != c2 để tạo một cung tiên quyết c1 -> c2, sau đó chạy đúng thuật toán Kahn! (Đừng quên bẫy đặc biệt: nếu w1 dài hơn w2 mà w2 lại là tiền tố của w1 như "abc" đứng trước "ab", trả về ngay không hợp lệ).
  2. 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ỳ.
  3. 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

  1. 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ốc 0 có hai nhánh 0 -> 1 -> 3 và 0 -> 2 -> 3, khi nhánh thứ nhất thăm xong 3 và quay lui, nếu bạn chỉ đánh dấu visited[3] = true rồi khi đi nhánh thứ hai 0 -> 2 -> 3 thấy visited[3] đã true mà 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).
  2. Đẩ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 đưa indeg[v] từ 2 xuống 1. Chỉ khi nào indeg[v] chạm đúng 0 thì mới được đẩy vào hàng đợi.
  3. Quên kiểm tra order.size() < n trước khi trả về mảng order trong 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 tra order.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 (4 môn, 4 cạnh → không phải chu trình, thứ tự 0 1 2 3).
  • Đồ thị 2 đỉnh khóa chéo 0 <-> 1 → in ra CYCLE.
  • Đồ 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 = 0 ngay từ đầu, in ra 0 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.

Muốn học bài bản cùng giảng viên?

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.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483