Course Schedule II: topological sort cuối cùng phải trả về thứ tự thực sự

Bài 207 hỏi câu hỏi có/không: liệu bạn có thể hoàn thành tất cả môn học? Bài này hỏi thêm một bước: trả về thứ tự cụ thể, hoặc mảng rỗng nếu chu trình làm điều đó bất khả thi. Đây là một sự thay đổi đáng kể — phát hiện chu trình là đủ trước đây; bây giờ bạn cần một topological order hợp lệ cho toàn bộ đồ thị.

Tin tốt: cả hai thuật toán từ bài 207 đều mở rộng tự nhiên. Cách DFS ba màu thu thập các node theo post-order rồi đảo ngược ở cuối. Kahn's BFS đã xây dựng thứ tự trong khi chạy. Không cái nào cần tư duy lại từ đầu.

Đề bài

Cho numCourses môn học được đánh nhãn từ 0 đến numCourses - 1 và danh sách các cặp điều kiện tiên quyết, trong đó [a, b] nghĩa là bạn phải học môn b trước môn a. Trả về một thứ tự hợp lệ để hoàn thành tất cả các môn học — hoặc mảng rỗng nếu chu trình làm điều đó bất khả thi. Xem đề đầy đủ: LeetCode 210.

Ràng buộc:
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= numCourses * (numCourses - 1)
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- ai != bi
- Tất cả các cặp [ai, bi] đều khác nhau.

Constraints nói gì trước khi viết code

1 <= numCourses <= 2000. Giống bài 207 — mọi môn học đều vừa trong mảng được index theo số môn. Không cần hash map cho đồ thị; mảng thông thường là đủ. Số đỉnh cũng cho biết O(V²) có thể chấp nhận được ở mức biên (4M phép toán), nhưng ta có thể làm O(V+E) và không có lý do gì để không dùng nó.

0 <= prerequisites.length <= numCourses * (numCourses - 1). Số cạnh có thể lên tới 2000 * 1999 = ~4M, tức là đồ thị dày đặc. Trong trường hợp dày đặc, adjacency list chiếm không gian tương tự adjacency matrix, nhưng các thuật toán vẫn là O(V+E). Trong trường hợp thưa thớt thông thường thì tốt hơn nhiều.

ai != bi — không có self-loop. Một môn học không thể là điều kiện tiên quyết của chính nó, nên bạn không bao giờ cần xử lý trường hợp tự-cycle thoái hóa.

Tất cả cặp đều khác nhau — không có cạnh trùng lặp. Xây dựng đồ thị rất thẳng thắn; không cần pass khử trùng.

Quy ước hướng: [a, b] có nghĩa là học b trước a. Cạnh đi từ b -> a. Tôi vẫn vẽ một hình nhỏ khi xây dựng đồ thị vì lấy ngược chiều là lỗi phổ biến nhất với bài toán này.

Với numCourses <= 2000, ngay cả thuật toán O(V+E) với hằng số lớn cũng ổn. Điều cần tránh là vòng lặp ngoài O(V²) tìm kiếm node chưa thăm bên trong vòng lặp trong O(E) — điều đó sẽ đẩy lên O(V²+E) không cần thiết.

DFS với ba màu và post-order collection

Ý tưởng: chạy DFS từ mọi node chưa thăm. Khi vào một node, đánh dấu nó GRAY (đang xử lý). Khi hoàn thành tất cả con cháu của nó, đánh dấu BLACK (đã xong) và thêm vào result. Nếu gặp node đang GRAY, có nghĩa là ta đã tìm thấy back edge — một chu trình — và answer là rỗng.

Tại sao thêm vào lúc BLACK lại cho topological order? Một node chỉ được đánh BLACK sau khi tất cả các môn phụ thuộc vào nó đã được xử lý xong. Vì vậy nếu môn A phải đến trước môn B, B sẽ hoàn thành và được thêm vào trước A. Điều đó có nghĩa là list result có A trước B theo chiều ngược — đó là lý do ta đảo ngược ở cuối.

from typing import List
 
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        for course, prereq in prerequisites:
            graph[prereq].append(course)
 
        WHITE, GRAY, BLACK = 0, 1, 2
        color = [WHITE] * numCourses
        result = []
        has_cycle = False
 
        def dfs(node: int) -> None:
            nonlocal has_cycle
            if color[node] == GRAY:
                has_cycle = True
                return
            if color[node] == BLACK:
                return
 
            color[node] = GRAY
            for neighbor in graph[node]:
                dfs(neighbor)
                if has_cycle:
                    return
 
            color[node] = BLACK
            result.append(node)
 
        for i in range(numCourses):
            if color[i] == WHITE:
                dfs(i)
                if has_cycle:
                    return []
 
        return result[::-1]

public class Solution {
    private const int WHITE = 0, GRAY = 1, BLACK = 2;
    private bool hasCycle = false;
 
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        List<int>[] graph = new List<int>[numCourses];
        for (int i = 0; i < numCourses; i++)
            graph[i] = new List<int>();
 
        foreach (var prereq in prerequisites)
            graph[prereq[1]].Add(prereq[0]);
 
        int[] color = new int[numCourses];
        var result = new List<int>();
 
        for (int i = 0; i < numCourses; i++) {
            if (color[i] == WHITE) {
                Dfs(i, graph, color, result);
                if (hasCycle) return new int[0];
            }
        }
 
        result.Reverse();
        return result.ToArray();
    }
 
    private void Dfs(int node, List<int>[] graph, int[] color, List<int> result) {
        if (color[node] == GRAY) { hasCycle = true; return; }
        if (color[node] == BLACK) return;
 
        color[node] = GRAY;
        foreach (int neighbor in graph[node]) {
            Dfs(neighbor, graph, color, result);
            if (hasCycle) return;
        }
 
        color[node] = BLACK;
        result.Add(node);
    }
}

Trace tay: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Đồ thị được xây dựng (chiều: prereq -> course):

Bắt đầu DFS từ node 0 (WHITE):

color[0] = GRAY
  neighbor 1: color[1] = GRAY
    neighbor 3: color[3] = GRAY
      không có neighbor
    color[3] = BLACK, result = [3]
  color[1] = BLACK, result = [3, 1]
  neighbor 2: color[2] = GRAY
    neighbor 3: color[3] == BLACK -> return ngay
  color[2] = BLACK, result = [3, 1, 2]
color[0] = BLACK, result = [3, 1, 2, 0]

Đảo ngược -> [0, 2, 1, 3]

Node 3 được thêm vào trước vì nó không có cạnh đi ra — không có gì phụ thuộc vào nó trong chuỗi phía sau, nhưng mọi thứ trong ví dụ này đều dẫn đến nó. Đảo ngược đặt root (0, không có prerequisites) lên đầu. Thứ tự cuối [0, 2, 1, 3] hợp lệ: môn 3 cần cả 1 và 2, cả hai cần 0, nên 0 phải đứng đầu.

Độ phức tạp

Time: O(V+E). Mỗi node được thăm đúng một lần (WHITE -> GRAY -> BLACK). Mỗi cạnh được duyệt đúng một lần từ trạng thái GRAY của nguồn.

Space: O(V+E). Adjacency list chiếm O(E). Mảng color chiếm O(V). Độ sâu call stack tối đa là O(V) trong trường hợp xấu nhất (chuỗi tuyến tính). Result list là O(V).

Kahn's algorithm: BFS từ in-degree bằng không

Kahn's lật ngược góc nhìn. Thay vì đi sâu vào các dependency, bạn bắt đầu từ các môn không có prerequisites và bóc từng lớp. Một bộ đếm in-degree theo dõi số prerequisites còn lại của mỗi môn. Khi bộ đếm đó về 0, môn đó sẵn sàng để học.

Không còn node nào có in-degree bằng không nhưng vẫn còn môn chưa xử lý? Điều đó có nghĩa là tất cả các môn còn lại đều liên quan đến chu trình — chúng đều có ít nhất một dependency còn tồn tại, và các dependency đó trỏ ngược lại chúng. Trong trường hợp đó, result.length < numCourses và ta trả về rỗng.

Điều quan trọng: Kahn's tạo ra topological order trực tiếp — không cần đảo ngược. Bạn thêm mỗi node vào result ngay khi nó trở nên sẵn sàng.

from collections import deque
from typing import List
 
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses
 
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1
 
        queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
        result = []
 
        while queue:
            current = queue.popleft()
            result.append(current)
            for neighbor in graph[current]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
 
        return result if len(result) == numCourses else []

public class Solution {
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        var graph = new List<int>[numCourses];
        int[] inDegree = new int[numCourses];
 
        for (int i = 0; i < numCourses; i++)
            graph[i] = new List<int>();
 
        foreach (var prereq in prerequisites) {
            graph[prereq[1]].Add(prereq[0]);
            inDegree[prereq[0]]++;
        }
 
        var queue = new Queue<int>();
        for (int i = 0; i < numCourses; i++)
            if (inDegree[i] == 0) queue.Enqueue(i);
 
        var result = new List<int>();
 
        while (queue.Count > 0) {
            int current = queue.Dequeue();
            result.Add(current);
            foreach (int neighbor in graph[current]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) queue.Enqueue(neighbor);
            }
        }
 
        return result.Count == numCourses ? result.ToArray() : new int[0];
    }
}

Trace tay: cùng ví dụ

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

graph:     0->[1,2], 1->[3], 2->[3], 3->[]
in_degree: [0, 1, 1, 2]

queue = [0]  (chỉ node có in_degree = 0)
result = []

Bước 1: dequeue 0 -> result = [0]
  neighbor 1: in_degree[1] = 1-1 = 0 -> enqueue 1
  neighbor 2: in_degree[2] = 1-1 = 0 -> enqueue 2
  queue = [1, 2]

Bước 2: dequeue 1 -> result = [0, 1]
  neighbor 3: in_degree[3] = 2-1 = 1 -> chưa sẵn sàng
  queue = [2]

Bước 3: dequeue 2 -> result = [0, 1, 2]
  neighbor 3: in_degree[3] = 1-1 = 0 -> enqueue 3
  queue = [3]

Bước 4: dequeue 3 -> result = [0, 1, 2, 3]
  không có neighbor
  queue = []

len(result) == 4 == numCourses -> return [0, 1, 2, 3]

Không cần đảo ngược. Thứ tự xuất hiện tự nhiên: bạn không thể xử lý một node cho đến khi tất cả prerequisites của nó xong, và bạn xử lý nó ngay khi chúng xong.

Độ phức tạp

Time: O(V+E). Mỗi node vào và ra queue đúng một lần. Mỗi cạnh được duyệt đúng một lần khi giảm in-degree.

Space: O(V+E). Adjacency list O(E), mảng in-degree O(V), queue tối đa O(V), result O(V).

Các edge case quan trọng

Không có prerequisites (prerequisites = []): in-degree bằng không cho mọi node. Kahn's enqueue tất cả numCourses node ngay lập tức và drain chúng theo thứ tự 0..numCourses-1. DFS thăm mọi node riêng lẻ, thêm theo thứ tự thăm, đảo ngược. Cả hai trả về thứ tự hợp lệ (tuy tùy ý).

Một môn học (numCourses = 1, prerequisites = []): cả hai cách đều trả về [0] ngay lập tức. Kahn's đặt 0 vào queue, dequeue nó, result length bằng 1. DFS chạy từ 0, không có neighbor, thêm 0, đảo ngược thành [0].

Có chu trình (ví dụ: prerequisites = [[0,1],[1,0]]): Kahn's không bao giờ enqueue node nào — cả hai đều có in-degree 1 và không cái nào về 0. result.length = 0 != 2, trả về []. DFS vào node 0, đánh GRAY, vào node 1, đánh GRAY, rồi thấy 0 đang GRAY và đặt has_cycle = True, unwind và trả về []. Cùng kết quả, cơ chế phát hiện khác nhau.

Đồ thị không liên thông: nếu các môn tạo thành nhiều thành phần độc lập không có cạnh nối, cả hai thuật toán đều xử lý đúng. Vòng lặp ngoài của DFS phủ mọi node WHITE bất kể kết nối. Kahn's enqueue mọi node có in-degree bằng không ngay từ đầu, bao phủ tất cả thành phần.

Mật độ tối đa (prerequisites.length = numCourses * (numCourses - 1)): đây là đồ thị có hướng đầy đủ. Nếu có chu trình, cả hai trả về [] nhanh chóng. Nếu bằng cách nào đó nó là acyclic (đòi hỏi một tổng thứ tự chặt chẽ), cả hai sẽ xử lý tất cả cạnh. Giới hạn O(V+E) vẫn giữ nguyên; chỉ là E lúc này lớn.

Bảng so sánh

Cùng chi phí tiệm cận, cấu trúc khác nhau đáng kể.

Cái nào tôi thực sự sẽ dùng

Kahn's. Mọi lúc, không cần suy nghĩ nhiều.

Lý do là thực tế. Kahn's tạo ra kết quả theo thứ tự đúng mà không cần bước đảo ngược cuối cùng — bước đảo ngược trong DFS là nguồn gây bug khó phát hiện trong test vì test case thường chấp nhận bất kỳ thứ tự hợp lệ nào. Kahn's cũng dùng queue tường minh thay vì recursion, có nghĩa là bạn không có nguy cơ vượt giới hạn recursion mặc định của Python trên input lớn (Python mặc định giới hạn 1000; với numCourses = 2000 và chuỗi tuyến tính thoái hóa, DFS sẽ vượt quá đó). Phiên bản C# tránh được vấn đề đó, nhưng trong Python đây là mối lo ngại thực sự.

Phiên bản DFS đáng hiểu vì cycle detection ba màu là kỹ thuật độc lập bạn sẽ dùng lại — nó xuất hiện trong các bài phát hiện back edge trong đồ thị có hướng tổng quát. Nhưng với bài toán cụ thể này, nơi bạn chỉ cần một topological order hợp lệ, Kahn's sạch hơn và ít dễ sai hơn.

Pattern nền: topological sort trên DAG

Cả hai cách tiếp cận đều là biểu hiện của cùng một pattern khái niệm: tuyến tính hóa directed acyclic graph sao cho mọi cạnh u -> v có u trước v trong output. Pattern này xuất hiện ở bất cứ đâu có dependency — hệ thống build giải quyết thứ tự biên dịch, package manager giải quyết thứ tự cài đặt, task scheduler thực thi ràng buộc ưu tiên.

Hai cách cài đặt chuẩn của topological sort ánh xạ vào hai traversal đồ thị kinh điển: DFS post-order (thu thập sau khi hoàn thành tất cả con cháu, đảo ngược ở cuối) và BFS theo in-degree (Kahn's). Mọi bài topological sort bạn gặp sẽ là biến thể của một trong hai cái này.

Kiểm tra chu trình không tách rời topological sort — nó vốn có trong đó. Một topological order tồn tại khi và chỉ khi đồ thị là DAG. Ngay khi bạn thử topological sort và gặp node GRAY (DFS) hoặc cạn queue với các node chưa đếm còn lại (Kahn's), bạn biết thuộc tính DAG thất bại.

Vị trí trong series và những gì tiếp theo

Trong series graphs, đây là bài topological sort thứ ba trong một cụm. Course Schedule (207) giới thiệu câu hỏi phát hiện chu trình. Bài này (210) thêm yêu cầu trả về thứ tự thực sự. Kỹ thuật giống nhau; hợp đồng output chặt chẽ hơn.

Course Schedule (207) là bài trực tiếp trước. Nếu 207 cảm thấy thoải mái, bài này thêm đúng một thứ: lưu và đảo ngược output DFS, hoặc đọc trực tiếp kết quả Kahn's. Công việc thêm là tối thiểu.

Alien Dictionary (LeetCode 269) là bước leo thang tự nhiên. Bạn được cho danh sách các từ đã sắp xếp theo bảng chữ cái ngoài hành tinh; bạn phải tái tạo thứ tự ký tự. Bài toán vẫn là topological sort trên DAG — bạn xây dựng cạnh từ các từ liền kề có ký tự khác nhau — nhưng giờ bạn phải tự xây dựng đồ thị thay vì được cho danh sách cạnh. Cùng pattern Kahn's áp dụng.

Sequence Reconstruction (LeetCode 444) hỏi liệu một chuỗi nhất định có phải là supersequence ngắn nhất duy nhất từ đó tất cả các subsequence được cho có thể được tái tạo — tương đương với hỏi liệu có tồn tại topological order duy nhất không. Nó buộc bạn suy nghĩ về khi nào sự mơ hồ in-degree bằng không có nghĩa là có nhiều thứ tự hợp lệ.

Parallel Courses (LeetCode 1136) thêm twist: các môn ở cùng level (trong cùng wave BFS của Kahn's) có thể học song song. Đáp án là số wave BFS — độ dài của critical path qua DAG. Đây là mở rộng trực tiếp của Kahn's algorithm nơi bạn theo dõi độ sâu wave thay vì chỉ thu thập thứ tự.