Disjoint Set Union — Near-O(1) với path compression + union by rank

TL;DR: Disjoint Set Union (DSU) quản lý tập hợp rời rạc với hai operation: find(x) — trả representative (root) của set chứa x; union(x, y) — gộp hai set. Cấu trúc chỉ dùng một mảng parent[], nhưng với hai optimization cộng hưởng — path compression (sau mỗi find, gán thẳng parent tới root) và union by rank (attach cây thấp vào cây cao) — đạt amortized O(α(n)) per operation, α là inverse Ackermann, thực tế nhỏ hơn hoặc bằng 4 với mọi n. Không có optimization nào đạt được giới hạn này đơn lẻ — phải kết hợp cả hai.

Lesson 08 đã dùng DSU như một black box trong Kruskal: find(x) trả root của component chứa x, union(x, y) gộp hai component, và ghi chú complexity "O(α(V)) amortized". Vậy α là gì, và tại sao một mảng số nguyên đơn giản lại đạt hiệu năng gần bằng hằng số?

Câu trả lời nằm ở hai optimization cộng hưởng nhau: path compression (mỗi lần tìm root, gán thẳng parent tới root để lần sau nhanh hơn) và union by rank (khi gộp, luôn attach cây nhỏ vào cây lớn để giữ chiều cao thấp). Riêng lẻ, mỗi optimization cho O(log n). Kết hợp, chúng đạt O(α(n)) amortized — giới hạn tới inverse Ackermann, thực tế nhỏ hơn hoặc bằng 4 với mọi n trong thực tế.

Bài này dạy DSU từ naive O(n²) lên optimized α(n), 2 optimization (path compression + union by rank), pseudocode đầy đủ, ứng dụng trong Kruskal MST, image segmentation, và friend circle problem.

1. Analogy — Cây gia phả tìm tổ tiên chung

Tưởng tượng một tập người, mỗi người có đúng một "parent" — người cha hoặc mẹ. Người ở gốc cây gia phả thì parent là chính mình. Để biết hai người có cùng dòng họ không, ta đi ngược lên parent chain của từng người đến gốc — nếu cùng gốc, cùng dòng họ.

Find tương đương hỏi "tổ tiên xa nhất của người này là ai?" — đi lên từng bước cho đến khi gặp người có parent là chính mình.

Union tương đương "kết hợp hai dòng họ thành một" — đặt gốc của dòng họ này làm con của gốc dòng họ kia.

Path compression tương đương "sau khi tìm ra tổ tiên xa nhất, mọi người trên đường đi đó cập nhật thẳng parent của mình tới tổ tiên đó" — lần sau hỏi lại sẽ trả lời ngay lập tức.

2. API của DSU

Ba operation cốt lõi:

• find(x) — trả root (representative) của set chứa x. Hai phần tử cùng set khi và chỉ khi find(x) = find(y).
• union(x, y) — gộp set chứa x với set chứa y. Trả true nếu thực sự merge (hai phần tử chưa cùng set), false nếu đã cùng set rồi.
• connected(x, y) — trả true nếu x và y cùng set. Tương đương find(x) = find(y).

-- Ví dụ sử dụng -- DSU trên 5 phần tử: {0, 1, 2, 3, 4}
DSU dsu <- khởi tạo với 5 phần tử
dsu.union(0, 1)       -- gộp set chứa 0 và set chứa 1
dsu.union(2, 3)       -- gộp set chứa 2 và set chứa 3
dsu.connected(0, 1)   -- true -- cùng set
dsu.connected(0, 2)   -- false -- khác set
dsu.union(1, 2)       -- gộp hai nhóm lại
dsu.connected(0, 3)   -- true -- giờ tất cả cùng một set

3. Naive implementation — và tại sao O(n²)

Ý tưởng cơ bản: parent[i] = i có nghĩa là i là root của set của mình. find(x) đi lên parent chain đến khi parent[x] = x. union(x, y) set root của x làm parent của root của y.

DSU_naive_find(parent, x):
    while parent[x] != x:
        x <- parent[x]    -- đi lên parent chain
    return x

DSU_naive_union(parent, x, y):
    rx <- DSU_naive_find(parent, x)
    ry <- DSU_naive_find(parent, y)
    if rx = ry: return false    -- đã cùng set
    parent[rx] <- ry            -- attach root của x vào root của y
    return true

Time: O(n) worst case mỗi find Space: O(n)

Worst case — chuỗi chain: nếu liên tục union theo chiều nhất định, cây DSU degenerate thành linked list dài n. Ví dụ: union(0,1), union(1,2), union(2,3), ..., union(n-2, n-1) tạo ra chuỗi 0 → 1 → 2 → ... → n-1. Khi đó find(0) cần đi qua n bước.

Tổng n lần union, mỗi lần cần gọi find tốn O(n) worst case → toàn bộ O(n²).

4. Optimization 1 — Union by Rank

Ý tưởng: khi gộp hai cây, attach cây thấp hơn vào cây cao hơn — giữ chiều cao toàn bộ cây ở O(log n). Nếu attach cây cao vào cây thấp, chiều cao tổng tăng thêm 1 không cần thiết.

rank[x] là một ước lượng chiều cao của cây gốc tại x. Khi hai cây có rank bằng nhau được gộp, rank của root mới tăng thêm 1. Khi rank khác nhau, attach root rank thấp vào root rank cao — rank không đổi.

DSU_rank_find(parent, x):
    while parent[x] != x:
        x <- parent[x]
    return x

DSU_rank_union(parent, rank, x, y):
    rx <- DSU_rank_find(parent, x)
    ry <- DSU_rank_find(parent, y)
    if rx = ry: return false
    -- Attach cây có rank thấp hơn vào cây có rank cao hơn
    if rank[rx] < rank[ry]:
        đổi chỗ rx và ry    -- đảm bảo rank[rx] >= rank[ry]
    parent[ry] <- rx
    if rank[rx] = rank[ry]:
        rank[rx] <- rank[rx] + 1
    return true

Time: O(log n) mỗi find Space: O(n)

Effect: chiều cao cây DSU tối đa log n sau bất kỳ sequence union nào. Do đó find(x) tốn O(log n). Tổng n operation: O(n log n). Cải thiện đáng kể so với O(n²), nhưng vẫn chưa phải tối ưu.

5. Optimization 2 — Path Compression

Ý tưởng: khi find(x) đi lên từ x đến root, mọi node trên đường đó đều biết root là gì. Tại sao không gán thẳng parent[x] = root cho chúng luôn? Lần find tiếp theo trên bất kỳ node nào trong đường đó sẽ tốn O(1).

Variant 1 — Full compression (đệ quy): đi lên root qua đệ quy, trên đường trở về set parent của từng node thẳng tới root.

DSU_compress_find(parent, x):
    if parent[x] != x:
        parent[x] <- DSU_compress_find(parent, parent[x])    -- compress khi quay về
    return parent[x]

Variant 2 — Path halving (iterative): mỗi bước, nhảy lên hai cấp (parent[parent[x]]) thay vì một. Không cần đệ quy. Thực tế cho cùng amortized complexity với full compression.

DSU_halving_find(parent, x):
    while parent[x] != x:
        parent[x] <- parent[parent[x]]    -- path halving -- nhảy qua một cấp
        x <- parent[x]
    return x

Time: O(log n) amortized (chỉ path compression) Space: O(n)

Effect (chỉ path compression, không union by rank): O(log n) amortized per operation. Cây bị "flatten" dần sau nhiều lần find, nhưng không có gì ngăn cây ban đầu cao tới O(n) trước khi được compress.

6. Combined — Union by Rank + Path Compression

DSU_init(parent, rank, n):
    for i <- 0 đến n-1:
        parent[i] <- i    -- mỗi phần tử là root của chính mình
        rank[i] <- 0

-- Full path compression -- đệ quy
DSU_find(parent, x):
    if parent[x] != x:
        parent[x] <- DSU_find(parent, parent[x])
    return parent[x]

-- Union by rank -- attach cây thấp vào cây cao
DSU_union(parent, rank, x, y):
    rx <- DSU_find(parent, x)
    ry <- DSU_find(parent, y)
    if rx = ry: return false
    if rank[rx] < rank[ry]:
        đổi chỗ rx và ry
    parent[ry] <- rx
    if rank[rx] = rank[ry]:
        rank[rx] <- rank[rx] + 1
    return true

DSU_connected(parent, x, y):
    return DSU_find(parent, x) = DSU_find(parent, y)

Time: O(α(n)) amortized mỗi operation Space: O(n)

Amortized complexity: O(α(n)) per operation, trong đó α là inverse Ackermann function.

α(n) là hàm tăng cực kỳ chậm:

• α(n) nhỏ hơn hoặc bằng 4 với n nhỏ hơn hoặc bằng 2^65536 (con số lớn hơn số nguyên tử trong vũ trụ).
• Trong mọi input thực tế: α(n) nhỏ hơn hoặc bằng 4.
• Thực tế coi như hằng số.

Đây là tight bound được chứng minh bởi Tarjan (1975) — bài báo "Efficiency of a Good But Not Linear Set Union Algorithm" chứng minh cả upper bound O(α(n)) lẫn lower bound, nghĩa là không thể cải thiện thêm với model này.

7. Trace ví dụ — step-by-step

Bắt đầu với DSU 5 phần tử (0 đến 4). parent = [0,1,2,3,4], rank = [0,0,0,0,0].

graph TD
    subgraph "Sau union(1,2) — rank[1]=1"
        A1((1)) --> A2((2))
    end
    subgraph "Sau union(3,4) — rank[3]=1"
        B3((3)) --> B4((4))
    end
    subgraph "Sau union(1,3) — rank[1]=2"
        C1((1)) --> C2((2))
        C1 --> C3((3))
        C3 --> C4((4))
    end
    subgraph "Sau find(4) — path compression"
        D1((1)) --> D2((2))
        D1 --> D3((3))
        D1 --> D4((4))
    end

Bước 1: union(1, 2)

• find(1) = 1, find(2) = 2 — khác nhau.
• rank[1] = rank[2] = 0 — attach 2 dưới 1, tăng rank[1] lên 1.
• parent = [0,1,1,3,4], rank = [0,1,0,0,0].

Bước 2: union(3, 4)

• find(3) = 3, find(4) = 4 — khác nhau.
• rank[3] = rank[4] = 0 — attach 4 dưới 3, tăng rank[3] lên 1.
• parent = [0,1,1,3,3], rank = [0,1,0,1,0].

Bước 3: union(1, 3)

• find(1) = 1, find(3) = 3 — khác nhau.
• rank[1] = rank[3] = 1 — attach 3 dưới 1, tăng rank[1] lên 2.
• parent = [0,1,1,1,3], rank = [0,2,0,1,0].
• Cây: root 1, con trực tiếp là 2 và 3, con của 3 là 4.

Bước 4: find(4)

• parent[4] = 3, parent[3] = 1, parent[1] = 1 — root là 1.
• Path compression: parent[4] = 1, parent[3] = 1 (đã là 1 rồi).
• parent = [0,1,1,1,1]. Node 4 giờ trỏ thẳng tới root.
• Lần sau gọi find(4): O(1) ngay lập tức.

8. Pitfall tổng hợp

Pitfall 1 — Chỉ dùng một trong hai optimization

Chỉ union by rank (không path compression) cho O(log n) per find — tốt, nhưng chưa phải tối ưu.

Chỉ path compression (không union by rank) cho O(log n) amortized per operation (theo phân tích Tarjan) — tốt, nhưng worst-case một lần find đầu tiên trên cây chưa compress vẫn tốn O(n), và không có gì ngăn cây ban đầu cao O(n) trước khi được compress lần đầu.

-- WRONG: chỉ union by rank, không path compression
DSU_find_wrong1(parent, x):
    while parent[x] != x:
        x <- parent[x]    -- O(log n) mỗi lần -- chưa tối ưu

-- WRONG: chỉ path compression, không union by rank
DSU_union_wrong2(parent, x, y):
    rx <- DSU_find(parent, x)
    ry <- DSU_find(parent, y)
    if rx = ry: return false
    parent[rx] <- ry    -- không kiểm tra rank -- cây vẫn có thể cao trước khi compress
    return true

Phải dùng cả hai để đạt O(α(n)). Trên 1 triệu operation: chênh lệch thực tế khoảng 4× so với chỉ dùng một optimization.

Pitfall 2 — Recursive find gây stack overflow

Trên input adversarial (chain dài trước khi compression lần đầu), recursion depth của find bằng chiều cao cây. Với n = 100.000 và cây chưa compress, có thể gây lỗi stack overflow (stack mặc định thường giới hạn vài trăm đến vài nghìn frame).

-- RISKY: độ sâu đệ quy = chiều cao cây, có thể stack overflow
DSU_find_recursive(parent, x):
    if parent[x] != x:
        parent[x] <- DSU_find_recursive(parent, parent[x])
    return parent[x]

-- SAFE: iterative two-pass full compression
DSU_find_safe(parent, x):
    root <- x
    while parent[root] != root:
        root <- parent[root]       -- pass 1: tìm root
    while parent[x] != root:      -- pass 2: compress
        next <- parent[x]
        parent[x] <- root
        x <- next
    return root

Time: O(α(n)) amortized Space: O(1) thêm (không stack)

Pitfall 3 — DSU không thread-safe

find vừa đọc vừa ghi parent[] (path compression). Nếu nhiều thread gọi find hoặc union đồng thời, race condition xảy ra:

-- RACE CONDITION: hai thread gọi union đồng thời
-- Thread A: find(x) đọc parent[x] = 3
-- Thread B: find(x) ghi parent[x] = 1 (path compression)
-- Thread A: ghi parent[x] = 5 (giá trị cũ, stale)
-- Kết quả: parent[x] không còn trỏ tới root -- find() trả kết quả sai

DSU với path compression không an toàn để dùng từ nhiều thread mà không có synchronization. Với concurrent use case, dùng lock hoặc thiết kế offline: collect tất cả query trước, chạy DSU single-threaded, trả kết quả.

9. Variants đáng biết

Weighted DSU (track size thay rank): thay rank[] bằng size[] — size[root] là số phần tử trong set đó. union attach set nhỏ hơn vào set lớn hơn. Cho phép query thêm "set này có bao nhiêu phần tử?" trong O(α(n)).

-- Query: số phần tử trong set chứa x
DSU_size(size, parent, x):
    return size[DSU_find(parent, x)]

Offline LCA (Lowest Common Ancestor) — Tarjan offline: bài toán tìm LCA cho nhiều cặp node trong cây, query offline. Dùng DSU để track "đã process component nào" trong DFS — cho O((V + Q) × α(V)) tổng với Q query.

DSU with rollback (Undo Union): cho phép "undo" các union theo thứ tự stack. Cần thiết cho persistent DS hoặc time-travel query (ví dụ offline dynamic connectivity). Đánh đổi: không thể dùng path compression (vì compress làm mất thông tin để rollback) — chỉ dùng union by rank, cho O(log n) per operation.

10. Ứng dụng thực tế

Kruskal MST (lesson 08): DSU detect cycle khi thêm edge. Với mỗi edge (u, v) trong danh sách đã sort, kiểm tra dsu.union(u, v) — nếu return false, u và v đã cùng component, thêm edge này sẽ tạo cycle. Hiệu năng DSU trực tiếp ảnh hưởng đến toàn bộ Kruskal: E lần gọi union × O(α(V)) = O(E × α(V)) — thực tế coi như O(E), không bottleneck sort O(E log E).

Image segmentation (computer vision): treat mỗi pixel là vertex, edge giữa hai pixel liền kề có weight là difference màu/độ sáng. Felzenszwalb-Huttenlocher algorithm (2004) dùng DSU: với mỗi edge theo thứ tự tăng dần của weight, kiểm tra xem hai pixel có đủ "khác nhau" để thuộc hai segment khác nhau không — nếu không, union chúng lại. Kết quả: mỗi root của DSU là một segment. DSU cho phép xử lý ảnh 4K (khoảng 8 triệu pixel) real-time.

Network connectivity (offline): social network với hàng triệu user, cần trả lời "A và B có kết nối không?" cho nhiều cặp. Xây DSU một lần trên toàn graph (O(E × α(V))), sau đó mỗi query chỉ tốn O(α(V)) ≈ O(1). Ứng dụng trong Facebook "People You May Know" feature và LinkedIn connection degree.

Compiler — register allocation: trong SSA (Static Single Assignment) form, các biến tạm cùng giá trị cần được assign vào cùng register. Track equivalence class của biến bằng DSU — union(a, b) khi phát hiện a và b phải cùng register. GCC và LLVM dùng union-find internally cho coalescing pass trong register allocator.

11. Deep Dive

12. Tóm tắt

• DSU dùng 1 mảng parent[]: parent[x] = x nghĩa là x là root của set mình.
• Naive (không optimization): find O(n) worst case khi cây degenerate thành chain → tổng O(n²).
• Union by rank: attach cây thấp vào cây cao → chiều cao tối đa log n → find O(log n).
• Path compression: sau mỗi find, gán parent[x] = root cho mọi node trên đường → lần sau O(1).
• Kết hợp cả hai: amortized O(α(n)) per operation. α(n) nhỏ hơn hoặc bằng 4 với mọi n thực tế — thực tế coi như hằng số.
• Recursive find có thể gây stack overflow trên chain dài — prefer iterative two-pass hoặc path halving.
• Không thread-safe: path compression vừa đọc vừa ghi parent[] — cần synchronization hoặc offline design khi dùng concurrent.
• Ứng dụng: Kruskal MST (cycle detection), image segmentation, network connectivity, compiler register allocation.

13. Tự kiểm tra

-- Thread A: find(5)
--   đọc: parent[5] = 3
--   đọc: parent[3] = 1 -> root = 1
--   ghi: parent[5] = 1  (path compress)

-- Thread B: đồng thời -- find(3)
--   đọc: parent[3] = 1 -> root = 1
--   union(3, 7): ghi parent[1] = 7 (root mới)

-- Bây giờ Thread A ghi parent[5] = 1 (root cũ, stale!)
-- parent[1] = 7 nhưng parent[5] = 1 -- find(5) trả 1, không phải 7 -> SAI

Bài tiếp theo: Mini-challenge: maze BFS + path reconstruction