Course Schedule: phát hiện chu trình là toàn bộ bài toán

Lần đầu gặp bài này tôi bắt đầu nghĩ đến simulation — một hàng đợi nào đó phát lại lịch học. Mất vài phút mới nhận ra câu hỏi không liên quan gì đến thời gian. Nó hỏi: đồ thị có hướng này có acyclic không? Nếu có, một thứ tự hợp lệ tồn tại và trả về true. Nếu không, có chuỗi điều kiện tiên quyết nào đó tạo thành vòng lặp và trả về false. Phần còn lại trong đề bài chỉ là ngữ cảnh.

Cách nhìn đó làm không gian giải pháp rõ ràng ngay. Cycle detection trong đồ thị có hướng có đúng hai cách tiếp cận đáng biết: DFS với three-color marking, và Kahn's algorithm dùng BFS cùng in-degree. Cả hai đều O(V+E). Ràng buộc nói numCourses <= 2000 và prerequisites.length <= 5000, nghĩa là ngay cả adjacency matrix cũng vừa vặn trong bộ nhớ — nhưng adjacency list là biểu diễn tự nhiên, và cả hai thuật toán xây dựng nó như nhau.

Những gì ràng buộc thực sự buộc phải làm

numCourses <= 2000. Các đỉnh vừa trong mảng được đánh chỉ số trực tiếp theo số khóa học. Không cần hash map; graph[i] chính là danh sách láng giềng của i.

prerequisites.length <= 5000. Đó là số cạnh. Kết hợp với 2000 đỉnh, đồ thị thưa — khoảng 2.5 cạnh mỗi đỉnh trung bình. Adjacency list là biểu diễn đúng; adjacency matrix sẽ lãng phí 2000 × 2000 = 4M ô cho 5000 cạnh.

Tất cả các cặp là unique. Không có cạnh trùng lặp, nên không cần deduplicate lúc xây dựng.

[a, b] có nghĩa là "học b trước a" — hướng cạnh là b -> a. Tôi đã nhầm cái này trước đây. Cách tôi ghi nhớ: b là kẻ chặn, a là khóa học bị chặn, nên mũi tên đi từ kẻ chặn đến bị chặn: b -> a.

DFS với three-color marking

Cách tiếp cận cycle detection cổ điển cho đồ thị có hướng gán mỗi node một trong ba trạng thái: chưa thăm (0), đang trong DFS stack hiện tại (1), đã xử lý hoàn toàn (2). Kiểm tra chu trình đơn giản: nếu DFS đến một node vẫn ở trạng thái 1 — vẫn trên đường đi hiện tại — bạn vừa tìm thấy back edge, nghĩa là chu trình.

Tại sao ba màu chứ không phải hai? Với hai màu (đã thăm / chưa thăm), bạn không thể phân biệt "tôi đã thăm node này trong một lần DFS trước" với "tôi đang ở giữa một đường đi đi qua node này." Trường hợp đầu là an toàn. Trường hợp hai là chu trình. Hai màu gộp chúng lại; ba màu tách chúng ra.

Trace tay qua Example 2: numCourses = 2, prerequisites = [[1,0],[0,1]].

Xây đồ thị: cạnh 0->1 (từ pair [1,0]) và cạnh 1->0 (từ pair [0,1]).

graph[0] = [1]
graph[1] = [0]
states = [0, 0]

Gọi has_cycle(0):

• states[0] là 0, đặt thành 1. states = [1, 0]
• Đệ quy vào láng giềng 1: gọi has_cycle(1)
  • states[1] là 0, đặt thành 1. states = [1, 1]
  • Đệ quy vào láng giềng 0: gọi has_cycle(0)
    • states[0] là 1 -> phát hiện chu trình, return True
  • Truyền True lên
• has_cycle(0) trả về True, vòng lặp chính trả về False

Trace cho Example 1: numCourses = 2, prerequisites = [[1,0]].

graph[0] = [1]
graph[1] = []
states = [0, 0]

Gọi has_cycle(0):

• states[0] = 1. Đệ quy vào 1.
  • states[1] = 1. Không có láng giềng. Đặt states[1] = 2. Return False.
• states[0] = 2. Return False.

Gọi has_cycle(1): states[1] đã là 2, return False ngay lập tức.

Không tìm thấy chu trình, return True.

from typing import List
 
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        for course, prereq in prerequisites:
            graph[prereq].append(course)
 
        # 0: chưa thăm, 1: đang thăm (trong stack hiện tại), 2: đã xử lý hoàn toàn
        states = [0] * numCourses
 
        def has_cycle(course: int) -> bool:
            if states[course] == 1:
                return True
            if states[course] == 2:
                return False
 
            states[course] = 1
            for neighbor in graph[course]:
                if has_cycle(neighbor):
                    return True
            states[course] = 2
            return False
 
        for course in range(numCourses):
            if states[course] == 0 and has_cycle(course):
                return False
 
        return True

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        var graph = new List<int>[numCourses];
        for (int i = 0; i < numCourses; i++)
            graph[i] = new List<int>();
 
        foreach (var p in prerequisites)
            graph[p[1]].Add(p[0]);
 
        // 0: chưa thăm, 1: đang thăm, 2: đã xử lý hoàn toàn
        var states = new int[numCourses];
 
        bool HasCycle(int course) {
            if (states[course] == 1) return true;
            if (states[course] == 2) return false;
 
            states[course] = 1;
            foreach (int neighbor in graph[course])
                if (HasCycle(neighbor)) return true;
            states[course] = 2;
            return false;
        }
 
        for (int course = 0; course < numCourses; course++)
            if (states[course] == 0 && HasCycle(course))
                return false;
 
        return true;
    }
}

Thời gian: O(V+E) — mỗi đỉnh được xử lý hoàn toàn nhiều nhất một lần (trạng thái 2 short-circuit tất cả các lần thăm tiếp theo), mỗi cạnh được duyệt nhiều nhất một lần trong quá trình xử lý đó. Không gian: O(V+E) cho adjacency list cộng O(V) cho mảng states và recursion call stack — worst case độ sâu stack O(V) cho chuỗi tuyến tính các khóa học.

Một vấn đề thực tế: giới hạn recursion mặc định của Python là 1000. Với numCourses lên đến 2000 và chuỗi tuyến tính, bạn sẽ chạm vào giới hạn này. Trong thực tế tôi sẽ dùng sys.setrecursionlimit(3000) hoặc chuyển sang cách tiếp cận Kahn's iterative bên dưới. C# có call stack sâu hơn nhiều và không gặp vấn đề này ở kích thước input này.

Kahn's algorithm: BFS topological sort

Cách tiếp cận thứ hai không tìm kiếm chu trình trực tiếp. Thay vào đó nó cố xây dựng một topological ordering hợp lệ, và kiểm tra trở thành: nếu bạn có thể sắp xếp tất cả các khóa học, không có chu trình; nếu bị kẹt với các khóa học chưa xử lý, một chu trình đang bẫy chúng.

Cơ chế nằm ở in-degree. In-degree của một node là số cạnh đi vào nó — số điều kiện tiên quyết của khóa học đó. Một khóa học có in-degree 0 không có điều kiện tiên quyết; nó có thể học ngay lập tức. Học nó, xóa khỏi đồ thị (giảm in-degree của mỗi khóa học phụ thuộc vào nó), và lặp lại. Bất kỳ khóa học nào đạt in-degree 0 sau đó sẽ vào queue.

Nếu đồ thị có chu trình, các node trong chu trình đó sẽ không bao giờ đạt in-degree 0 — mỗi node vẫn phụ thuộc vào ít nhất một node khác trong chu trình. Chúng sẽ không bao giờ vào queue. Số đếm processed sẽ thiếu so với numCourses.

Trace đầy đủ qua ví dụ phong phú hơn: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]].

Danh sách cạnh (b -> a từ mỗi pair):
  [1,0] -> 0 -> 1
  [2,0] -> 0 -> 2
  [3,1] -> 1 -> 3
  [3,2] -> 2 -> 3

graph[0] = [1, 2]
graph[1] = [3]
graph[2] = [3]
graph[3] = []

in_degree = [0, 1, 1, 2]

Queue khởi đầu: các khóa học có in-degree 0 -> [0]. processed = 0.

Bước 1: pop 0. processed = 1. Láng giềng: 1, 2. Giảm in_degree[1] -> 0, in_degree[2] -> 0. Cả hai vào queue. Queue = [1, 2].

Bước 2: pop 1. processed = 2. Láng giềng: 3. Giảm in_degree[3] -> 1. Chưa bằng 0. Queue = [2].

Bước 3: pop 2. processed = 3. Láng giềng: 3. Giảm in_degree[3] -> 0. Vào queue. Queue = [3].

Bước 4: pop 3. processed = 4. Không có láng giềng. Queue = [].

processed (4) == numCourses (4). Trả về True.

Trường hợp chu trình: numCourses = 2, prerequisites = [[1,0],[0,1]].

graph[0] = [1], graph[1] = [0]
in_degree = [1, 1]

Queue bắt đầu rỗng — không có node nào có in-degree 0. Vòng while không bao giờ chạy. processed (0) != numCourses (2). Trả về False.

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

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        var graph = new List<int>[numCourses];
        var inDegree = new int[numCourses];
 
        for (int i = 0; i < numCourses; i++)
            graph[i] = new List<int>();
 
        foreach (var p in prerequisites) {
            graph[p[1]].Add(p[0]);
            inDegree[p[0]]++;
        }
 
        var queue = new Queue<int>();
        for (int i = 0; i < numCourses; i++)
            if (inDegree[i] == 0)
                queue.Enqueue(i);
 
        int processed = 0;
        while (queue.Count > 0) {
            int course = queue.Dequeue();
            processed++;
            foreach (int neighbor in graph[course]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0)
                    queue.Enqueue(neighbor);
            }
        }
 
        return processed == numCourses;
    }
}

Thời gian: O(V+E) — cùng lý luận như DFS. Mỗi node vào queue nhiều nhất một lần; mỗi cạnh được xem xét đúng một lần khi node nguồn của nó được dequeue. Không gian: O(V+E) cho đồ thị, O(V) cho in_degree và queue.

Edge cases

Không có prerequisites. prerequisites = []. Tất cả in-degree giữ nguyên 0; mọi khóa học vào queue ngay lập tức. Kahn's xử lý tất cả numCourses khóa học. DFS gọi has_cycle cho mỗi khóa học và ngay lập tức đặt nó về trạng thái 2 mà không có lời gọi đệ quy nào. Cả hai trả về True trong O(V).

Self-loop. Nếu [a, a] xuất hiện — khóa học yêu cầu chính nó. Ràng buộc nói pairs là unique và 0 <= ai, bi < numCourses nhưng không cấm tường minh a == b. Với DFS: has_cycle(a) đặt trạng thái thành 1, sau đó thấy láng giềng a đang ở trạng thái 1 — trả về True ngay. Với Kahn's: in_degree[a] bị tăng nhưng không bao giờ bị giảm bởi ai khác, nên không bao giờ đạt 0 và không bao giờ được xử lý. Cả hai xử lý đúng.

Đồ thị rời rạc. Nhiều nhóm khóa học độc lập không có prerequisites liên kết chúng. DFS xử lý qua vòng lặp ngoài: nó gọi has_cycle cho mỗi khóa học trong 0..numCourses-1, đảm bảo nó thăm mọi component dù chúng rời rạc. Kahn's xử lý vì mọi khóa học có in-degree 0 đều bắt đầu trong queue bất kể thuộc component nào.

Chuỗi tuyến tính. 0 -> 1 -> 2 -> ... -> n-1. Không có chu trình. DFS đi xuống toàn bộ chuỗi đệ quy — độ sâu stack đạt n-1. Với numCourses = 2000, đây là 1999 frame, vượt quá stack mặc định của Python. Kahn's hoàn toàn iterative và xử lý điều này không có vấn đề.

Tất cả khóa học trong một chu trình lớn. 0 -> 1 -> 2 -> ... -> n-1 -> 0. Kahn's: không có node nào đạt in-degree 0, queue rỗng từ đầu, processed giữ nguyên 0. DFS: đang thăm node 0, đi xuống toàn bộ chuỗi, sau đó gặp node 0 lại ở trạng thái 1 — phát hiện chu trình.

Cái nào nên ship

Nếu câu hỏi chỉ là "bạn có thể hoàn thành không?" và bạn thoải mái với recursion, DFS trực tiếp hơn một chút để lý luận — bạn đang theo sát từng chuỗi điều kiện tiên quyết và tìm back edge. Logic ba màu gọn gàng.

Tôi sẽ ship Kahn's. Lý do nhàm chán nhưng thực tế: nó iterative, nên không có vấn đề recursion limit; nó tạo ra topological order như side effect (hữu ích khi Course Schedule II xuất hiện trong buổi phỏng vấn tiếp theo); và điều kiện kết thúc là một phép so sánh duy nhất thay vì một boolean được truyền qua các lời gọi đệ quy. Code có độ dài tương đương. Không có lý do gì để ưa DFS hơn ở đây trừ khi bạn ở trong ngôn ngữ mà recursion overhead quan trọng hơn clarity.

Pattern và nơi nó xuất hiện

Đây là bài toán topological sort / DAG validation kinh điển. Mental model: bất cứ khi nào bạn có một tập hợp các mục với ràng buộc thứ tự và bạn cần biết thứ tự hợp lệ có tồn tại không, bạn đang nhìn vào cấu trúc này. Xây đồ thị dependency, kiểm tra chu trình.

Series xây dựng trực tiếp trên điều này. Bước tiếp theo là Course Schedule II (LeetCode 210), giống hệt ngoại trừ bạn cũng trả về thứ tự thực tế — Kahn's mở rộng sang điều này một cách tầm thường bằng cách thu thập các node được dequeue. Graph Valid Tree (LeetCode 261) đưa cycle detection tương tự vào đồ thị vô hướng, nơi kiểm tra thay đổi một chút — một undirected back edge là chu trình, nhưng bạn phải cẩn thận để không gắn nhãn cạnh bạn vừa đến từ đó. Alien Dictionary (LeetCode 269) dùng cùng topological sort nhưng buộc bạn tự xây đồ thị từ các so sánh cặp từ, đó là phần khó hơn của bài đó. Find Eventual Safe States (LeetCode 802) đảo ngược câu hỏi — thay vì hỏi liệu toàn bộ đồ thị có acyclic không, nó hỏi node nào không bao giờ có thể đến được chu trình.

Cả bốn bài đó trở nên đơn giản khi bạn có thể implement cả hai giải pháp ở đây mà không cần nghĩ nhiều.