Chương 13 - Topological Sort

Topological Sort sắp xếp đỉnh của DAG (Directed Acyclic Graph) sao cho mọi cạnh u → v thì u đứng trước v trong thứ tự. Đây là pattern bắt buộc cho mọi bài “hoàn thành theo thứ tự phụ thuộc”: build system, task scheduler, course prerequisites, …

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Chiều cạnh: a before b → cạnh a → b (tích luỹ indegree của b).
  • Phân biệt Kahn (BFS, indegree) vs DFS 3-color.
  • Phát hiện cycle: nếu len(order) != V → có chu trình.
  • Pattern uniqueness: queue size == 1 ở mỗi level → topo order duy nhất.

Quy ước hướng cạnh

Một trong những lỗi phổ biến nhất khi giải topo sort là vẽ cạnh sai chiều. Vì lý do này, toàn bộ sách dùng một quy ước duy nhất:

Mô tả thực tế              Cạnh trong graph        Indegree
─────────────────────────────────────────────────────────────
"a must come before b"     a → b                   indeg[b] += 1
"b depends on a"           a → b                   indeg[b] += 1
"a is prerequisite of b"   a → b                   indeg[b] += 1
─────────────────────────────────────────────────────────────
LC 207/210 input:          prerequisites[i] = [course, prereq]
                           tức là [b, a] dạng "to do b, must do a"
                           → cạnh a → b (prereq → course)
─────────────────────────────────────────────────────────────
LC 269 Alien Dict:         words[i] < words[i+1] theo lex
                           → ký tự khác nhau đầu tiên: c1 < c2
                           → cạnh c1 → c2

Kahn’s invariant: Pop node có indeg == 0 ↔︎ “không còn ai phải xong trước nó”.

Mọi bài Topo trong cuốn sách dùng convention u → v nghĩa là u xong trước v. Khi gặp đề có wording khác, bước đầu tiên nên là vẽ 2–3 cạnh ra giấy để kiểm tra rằng hướng cạnh trong code khớp đúng với mô tả của đề bài.

Khi nào dùng pattern này?

  • Bài có dependency rõ ràng: “A xong rồi mới làm B”.
  • Cần kiểm tra DAG có không (có chu trình → không có topo order).
  • Tính min levels để hoàn thành (Kahn’s BFS đếm số layer).
  • Kết hợp với DP - Chương 43.

2 thuật toán kinh điển:

  1. Kahn’s algorithm (BFS) - đếm indegree, đẩy node có indeg=0 vào queue.
  2. DFS với post-order - duyệt DFS, push node vào stack khi xong; reverse stack.

Cả 2 đều O(V + E). Mặc định mình dùng Kahn vì nó dễ extend cho “min levels”.

Template code 

from collections import defaultdict, deque
from typing import List

def topo_sort_kahn(n: int, edges: List[tuple]) -> List[int]:
    graph = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1

    queue = deque(i for i in range(n) if indeg[i] == 0)
    order: list[int] = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)

    return order if len(order) == n else []     # rỗng = có chu trình

Bài tự luyện cuối chương

  • LC 207 - Course Schedule (Chương 9)
  • LC 802 - Find Eventual Safe States
  • LC 851 - Loud and Rich
  • LC 1462 - Course Schedule IV
  • LC 1857 - Largest Color Value (Chương 43)
  • LC 2050 - Parallel Courses III (Chương 43)

13.1 Course Schedule II (LC 210)

Đề bài

Cho numCourses khoá và prerequisites[i] = [a, b] (học a cần b xong trước). Trả về thứ tự học hợp lệ, hoặc [] nếu có chu trình.

Ví dụ 

Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3]   (hoặc [0, 2, 1, 3])
Giải thích:
  Cạnh: 0 → 1, 0 → 2, 1 → 3, 2 → 3.

Ràng buộc

  • 1 <= numCourses <= 2000
  • 0 <= len(prerequisites) <= 5000

Clarifying questions

  • Có chu trình? → Trả [].
  • Nhiều topo order valid? → Chỉ cần trả 1 cái.

Hướng tiếp cận

Kahn’s algorithm - y hệt template. Khi pop node, push vào order. Cuối: nếu len(order) == numCourses → trả order; ngược lại có chu trình.

Hình minh hoạ với [[1,0],[2,0],[3,1],[3,2]]:

Graph:        0
             / \
            1   2
             \ /
              3

indeg ban đầu: [0, 1, 1, 2]
queue = [0]                   (indeg 0)

Pop 0 → order=[0]
  giảm indeg[1], indeg[2] → [_, 0, 0, 2]
  queue = [1, 2]

Pop 1 → order=[0, 1]
  giảm indeg[3] → [_, _, _, 1]

Pop 2 → order=[0, 1, 2]
  giảm indeg[3] → [_, _, _, 0]
  queue = [3]

Pop 3 → order=[0, 1, 2, 3]

len(order)=4=numCourses → trả [0, 1, 2, 3]  ✓

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        indeg = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            indeg[a] += 1

        queue = deque(i for i, d in enumerate(indeg) if d == 0)
        order: list[int] = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for nb in graph[node]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)

        return order if len(order) == numCourses else []

Phân tích độ phức tạp

  • Thời gian: O(V + E). Bộ nhớ: O(V + E).

Bình luận

  • Khác biệt với LC 207: chỉ thêm order.append(node). LC 207 chỉ check có DAG; LC 210 trả thứ tự cụ thể.
  • Bẫy hướng cạnh: “muốn học a cần b” → b → a. Vẽ rõ trước khi code.

Bài tự luyện liên quan

  • LC 207 - Course Schedule.
  • LC 802 - Find Eventual Safe States.
  • LC 1136 - Parallel Courses (bài 13.6).

13.2 Alien Dictionary (LC 269)

Đề bài

Một ngôn ngữ ngoài hành tinh dùng chữ cái Latin nhưng thứ tự khác. Cho danh sách words đã sắp xếp theo thứ tự đó. Hãy tìm 1 thứ tự chữ cái hợp lệ (string các chữ cái). Trả "" nếu mâu thuẫn.

Ví dụ 

Input:  words = ["wrt","wrf","er","ett","rftt"]
        (mảng từ đã sort theo thứ tự alphabet của ngôn ngữ ngoài hành tinh)
Output: "wertf"  (1 thứ tự chữ cái hợp lệ; có thể có nhiều đáp án)
Giải thích:
  wrt < wrf  → t < f
  wrf < er   → w < e
  er  < ett  → r < t
  ett < rftt → e < r
  → topo: w < e < r < t < f

Input:  words = ["z","x","z"]
Output: ""             (mâu thuẫn cyclic: z<x từ cặp 1 nhưng x<z từ cặp 2)

Ràng buộc

  • 1 <= len(words) <= 100
  • 1 <= len(words[i]) <= 100

Clarifying questions

  • Mâu thuẫn? → Trả ““.
  • Có ký tự không xuất hiện trong cặp nào? → Vẫn cần đưa vào output.

Hướng tiếp cận

2 bước:

  1. Trích quan hệ thứ tự từ các cặp (words[i], words[i+1]) liền kề:
    • Tìm vị trí ký tự đầu tiên khác nhau. Ký tự ở words[i] < ký tự ở words[i+1].
    • Trường hợp biên: nếu words[i] là tiền tố của words[i+1] thì OK, nhưng nếu words[i+1] là tiền tố thực sự của words[i] (vd ["abc", "ab"]) → mâu thuẫn → trả về "".
  2. Topological sort trên các quan hệ thu được.

Hình minh hoạ với ["wrt","wrf","er","ett","rftt"]:

Cặp 1: wrt vs wrf
  vị trí khác đầu: index 2 → t < f
  → cạnh t → f

Cặp 2: wrf vs er
  vị trí khác đầu: index 0 → w < e
  → cạnh w → e

Cặp 3: er vs ett
  vị trí khác đầu: index 1 → r < t
  → cạnh r → t

Cặp 4: ett vs rftt
  vị trí khác đầu: index 0 → e < r
  → cạnh e → r

Graph: w → e → r → t → f
Topo: w, e, r, t, f → "wertf"

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Khởi tạo indeg cho tất cả ký tự xuất hiện.
        indeg = {ch: 0 for w in words for ch in w}
        graph = defaultdict(set)

        # Trích quan hệ từ các cặp kề nhau.
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            # Edge case mâu thuẫn tiền tố.
            if len(w1) > len(w2) and w1.startswith(w2):
                return ""
            for c1, c2 in zip(w1, w2):
                if c1 != c2:
                    if c2 not in graph[c1]:
                        graph[c1].add(c2)
                        indeg[c2] += 1
                    break

        # Kahn's.
        queue = deque(ch for ch, d in indeg.items() if d == 0)
        order: list[str] = []
        while queue:
            ch = queue.popleft()
            order.append(ch)
            for nb in graph[ch]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)

        return ''.join(order) if len(order) == len(indeg) else ""

Phân tích độ phức tạp

  • Thời gian: O(C) với C = tổng số ký tự.
  • Bộ nhớ: O(1) (bảng chữ ≤ 26 - gần như constant).

Bình luận

  • 3 bẫy khó nhất:
    • Quên khởi tạo indeg cho tất cả ký tự xuất hiện (kể cả không có edge in) - nếu không, vòng final check len(order) == len(indeg) sai.
    • Quên check trùng cạnh trước khi tăng indeg - tăng đúp.
    • Quên trường hợp len(w1) > len(w2) and w1.startswith(w2) → tạo cấu trúc invalid.
  • Khi có nhiều topo order hợp lệ: đề chỉ yêu cầu 1 - Kahn’s tự nhiên trả về 1.

Bài tự luyện liên quan

  • LC 444 - Sequence Reconstruction (bài 13.5).
  • LC 953 - Verifying an Alien Dictionary (chỉ kiểm tra hợp lệ, không cần tìm thứ tự).

13.3 Minimum Height Trees (LC 310)

Đề bài

Input: n (số đỉnh) và edges: List[List[int]] - danh sách n-1 cạnh [u, v] mô tả tree vô hướng. Đỉnh đánh số 0..n-1.

Tìm tất cả root có thể chọn để chiều cao tree là min. Trả về danh sách root đó (có thể có 1 hoặc 2).

Ví dụ 

Input:  n=6, edges = [[0,3],[1,3],[2,3],[4,3],[5,4]]
Tree:    0   1   2
          \  |  /
           \ | /
             3
             |
             4
             |
             5
Output: [3, 4]

Ràng buộc

  • 1 <= n <= 2·10^4
  • edges.length == n - 1

Clarifying questions

  • n = 1? → Trả [0].
  • Forest hay tree? → Theo đề: tree (n-1 cạnh).

Hướng tiếp cận

Insight: Centroid của tree (gồm 1 hoặc 2 node) tối thiểu hoá chiều cao. Cách tìm: BFS từ các lá, “gọt vỏ” dần.

Quy trình: 1. Xây graph + tính degree.

  1. Đẩy mọi lá (degree == 1) vào queue. 3. Lặp: pop một lớp lá, giảm degree hàng xóm, lá mới (degree == 1) → queue. 4. Khi còn ≤ 2 node → đó là centroid(s).

Hình minh hoạ:

Lớp đầu - lá: [0, 1, 2, 5]
Gọt → còn lại: [3, 4]
                3 (degree=1 sau gọt), 4 (degree=1 sau gọt)
→ ≤ 2 node → centroids = [3, 4]

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        graph = defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        leaves = deque(i for i in range(n) if len(graph[i]) == 1)
        remaining = n
        while remaining > 2:
            size = len(leaves)
            remaining -= size
            for _ in range(size):
                leaf = leaves.popleft()
                nb = next(iter(graph[leaf]))    # lá có đúng 1 hàng xóm
                graph[nb].remove(leaf)
                if len(graph[nb]) == 1:
                    leaves.append(nb)
        return list(leaves)

Phân tích độ phức tạp

  • Thời gian: O(V + E) = O(n).
  • Bộ nhớ: O(n).

Bình luận

  • Tại sao tối đa 2 centroid? Định lý đồ thị: centroid của tree ≤ 2.
  • Bẫy: quên xử lý n == 1 → graph rỗng, không có lá.

Bài tự luyện liên quan

  • LC 834 - Sum of Distances in Tree.
  • LC 207, 210 - Course Schedule (I, II).

13.4 Sort Items by Groups Respecting Dependencies (LC 1203)

Đề bài

Cho n items, mỗi item thuộc 1 group (group[i] = -1 nếu chưa thuộc nhóm nào, sẽ phân nhóm riêng). Cho beforeItems[i] = các item phải làm trước item i. Hãy sắp xếp items sao cho: - Tôn trọng beforeItems. - Các item cùng group đứng liền nhau.

Trả [] nếu không khả thi.

Ví dụ 

Input:  n=8, m=2, group=[-1,-1,1,0,0,1,0,-1], beforeItems=[[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

Ràng buộc

  • 1 <= m <= n <= 3·10^4
  • group[i] ∈ [-1, m-1]

Clarifying questions

  • Item có thể chưa thuộc group nào? → Có (group[i] = -1). Phải gán group riêng.

Hướng tiếp cận

Hai lần topo sort: 1. Sort các group với nhau (item-level edge i → j mà khác group → group-edge). 2. Trong mỗi group, sort các item của nó. 3. Concat kết quả: dùng order group, mỗi group ghi tất cả item của nó theo order item.

Pre-processing: mọi item có group[i] == -1 → gán group mới riêng để tránh “không nhóm” ảnh hưởng.

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    def sortItems(
        self, n: int, m: int,
        group: List[int], beforeItems: List[List[int]]
    ) -> List[int]:
        # Gán group riêng cho item -1.
        for i in range(n):
            if group[i] == -1:
                group[i] = m
                m += 1

        item_graph = defaultdict(list)
        item_indeg = [0] * n
        group_graph = defaultdict(set)
        group_indeg = defaultdict(int)

        for cur, befores in enumerate(beforeItems):
            for prev in befores:
                item_graph[prev].append(cur)
                item_indeg[cur] += 1
                if group[prev] != group[cur]:
                    if group[cur] not in group_graph[group[prev]]:
                        group_graph[group[prev]].add(group[cur])
                        group_indeg[group[cur]] += 1

        def topo(nodes, graph, indeg) -> List[int]:
            queue = deque(x for x in nodes if indeg[x] == 0)
            out: list = []
            while queue:
                x = queue.popleft()
                out.append(x)
                for nb in graph[x]:
                    indeg[nb] -= 1
                    if indeg[nb] == 0:
                        queue.append(nb)
            return out if len(out) == len(nodes) else []

        item_order = topo(range(n), item_graph, item_indeg)
        if not item_order:
            return []
        group_order = topo(range(m), group_graph, group_indeg)
        if not group_order:
            return []

        # Gom theo group theo thứ tự group, các item trong group giữ thứ tự item_order.
        bucket: dict[int, list[int]] = defaultdict(list)
        for item in item_order:
            bucket[group[item]].append(item)
        result: list[int] = []
        for g in group_order:
            result.extend(bucket[g])
        return result

Phân tích độ phức tạp

  • Thời gian: O(n + e_item + e_group).
  • Bộ nhớ: O(n + m + e).

Bình luận

  • Bài hard - pattern “lồng 2 lớp topo sort”. Nhận diện: bất cứ khi nào có “nhóm” mà thứ tự nhóm và thứ tự trong nhóm đều có constraint, hãy nghĩ đến 2 lớp topo.
  • Bẫy: quên gán group riêng cho -1 → nhiều item rời rạc nhập làm 1 nhóm sai.

Bài tự luyện liên quan

  • LC 210 - Course Schedule II.
  • LC 269 - Alien Dictionary.

13.5 Sequence Reconstruction (LC 444)

Đề bài

Cho nums (1 hoán vị của 1..n) và sequences (list các sub-sequence). Hãy kiểm tra nums có phải là topological order duy nhất suy ra từ sequences hay không.

Ví dụ 

Input:  nums = [1, 2, 3], sequences = [[1,2],[1,3]]
Output: False
Giải thích: từ [1,2] và [1,3] → có thể là [1,2,3] hoặc [1,3,2] → không unique.

Input:  nums = [1, 2, 3], sequences = [[1,2],[1,3],[2,3]]
Output: True

Ràng buộc

  • 1 <= n <= 10^4
  • nums là permutation 1..n
  • 1 <= len(sequences) <= 10^4

Clarifying questions

  • Sequence có thể có duplicate? → Theo đề: nums là permutation 1..n.

Hướng tiếp cận

Chạy Kahn’s. Để unique, mỗi level chỉ có đúng 1 node indeg == 0 - nếu có ≥ 2 ⇒ có nhiều topo order ⇒ False. Đồng thời thứ tự pop phải khớp nums.

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        n = len(nums)
        graph = defaultdict(set)
        indeg = [0] * (n + 1)
        for seq in sequences:
            for i in range(len(seq) - 1):
                u, v = seq[i], seq[i + 1]
                if v not in graph[u]:
                    graph[u].add(v)
                    indeg[v] += 1

        queue = deque(i for i in range(1, n + 1) if indeg[i] == 0)
        idx = 0
        while queue:
            if len(queue) > 1:
                return False              # >1 lựa chọn → không unique
            x = queue.popleft()
            if nums[idx] != x:
                return False              # khác thứ tự nums
            idx += 1
            for nb in graph[x]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    queue.append(nb)
        return idx == n

Phân tích độ phức tạp

  • Thời gian: O(V + E). Bộ nhớ: O(V + E).

Bình luận

  • Check len(queue) > 1 là cái twist của bài - uniqueness của topo order.
  • Bẫy: quên đếm trùng edge → indeg sai. Dùng set cho graph.

Bài tự luyện liên quan

  • LC 269 - Alien Dictionary.
  • LC 210 - Course Schedule II.

13.6 Parallel Courses (LC 1136)

Đề bài

Cho n khoá học và relations [a, b] (học a xong rồi học b). Mỗi semester bạn có thể học bất kỳ số khoá miễn đã hoàn thành prerequisite. Trả về số semester tối thiểu để học hết, hoặc -1 nếu có chu trình.

Ví dụ 

Input:  n=3, relations=[[1,3],[2,3]]
Output: 2
Giải thích: Semester 1 học [1,2], semester 2 học [3]

Ràng buộc

  • 1 <= n <= 5000
  • 0 <= len(relations) <= 5000

Clarifying questions

  • Có chu trình? → Trả -1.
  • n = 0? → Theo đề: n ≥ 1.

Hướng tiếp cận

Kahn’s BFS, nhưng đếm theo level (semester). Mỗi vòng outer of BFS xử lý toàn bộ queue hiện tại = các khoá có thể học cùng semester.

Code Python 3 

from collections import defaultdict, deque
from typing import List

class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        graph = defaultdict(list)
        indeg = [0] * (n + 1)
        for u, v in relations:
            graph[u].append(v)
            indeg[v] += 1

        queue = deque(i for i in range(1, n + 1) if indeg[i] == 0)
        taken = 0
        semesters = 0
        while queue:
            semesters += 1
            for _ in range(len(queue)):
                u = queue.popleft()
                taken += 1
                for v in graph[u]:
                    indeg[v] -= 1
                    if indeg[v] == 0:
                        queue.append(v)
        return semesters if taken == n else -1

Phân tích độ phức tạp

  • Thời gian: O(V + E). Bộ nhớ: O(V + E).

Bình luận

  • Pattern “BFS đếm level” áp được cho mọi bài “min steps with parallel execution”. Còn xuất hiện ở LC 2050 (Parallel Courses III) với constraint thời gian - sẽ giải bằng Tree DP (Chương 43).
  • Bẫy: taken phải = n; nếu chu trình → một số node không bao giờ rơi về indeg == 0.

Bài tự luyện liên quan

  • LC 2050 - Parallel Courses III (Chương 43).
  • LC 2115 - Find All Possible Recipes (Chương 43).

Tóm tắt chương & Quyết định

Topo + DP framing (cầu nối sang Chương 43)

  • Topo cho mình thứ tự an toàn để compute dp[node] chỉ dựa trên dp[predecessors].
  • Mọi bài Chương 43 (Largest Color Value, Longest Increasing Path, Parallel Courses III) đều theo cùng khung này.

Sequence Reconstruction (LC 444) - vì sao queue phải luôn có ≤ 1 phần tử?

  • Nếu tại bước nào đó queue có ≥ 2 ứng cử viên cùng indegree == 0, ta có thể chọn nhiều cách → không duy nhất.
  • Nếu queue luôn có đúng 1 phần tử và topo hết các node → duy nhất.

Alien Dictionary (LC 269) - invalid prefix case

Nếu w_i là prefix của w_{i-1} (vd ["abc", "ab"]), từ điển không hợp lệ → return "". Kiểm tra TRƯỚC khi build edges (đừng quên break đúng chỗ).

Sort Items by Groups (LC 1203) - DAG 2 lớp 

items 5,6 ∈ groupA   items 7,8 ∈ groupB   items 9 ∈ -1 (riêng)

Item DAG:  5 → 6,  7 → 8,  6 → 7   (intra + cross-group)
Group DAG: A → B   (vì 6 → 7 mà 6 ∈ A, 7 ∈ B)

→ Topo group order → trong mỗi group topo item order.