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

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à comment code ghi "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), code Java đầ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:

• int find(int 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).
• boolean union(int x, int 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.
• boolean connected(int x, int y) — trả true nếu x và y cùng set. Tương đương find(x) == find(y).

// Example usage -- union-find on 5 elements: {0, 1, 2, 3, 4}
DisjointSetUnion dsu = new DisjointSetUnion(5);
dsu.union(0, 1); // merge set containing 0 and set containing 1
dsu.union(2, 3); // merge set containing 2 and set containing 3
dsu.connected(0, 1); // true -- same set
dsu.connected(0, 2); // false -- different sets
dsu.union(1, 2);     // merge the two groups
dsu.connected(0, 3); // true -- now all in one 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.

public class DisjointSetNaive {
    private int[] parent;

    public DisjointSetNaive(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int find(int x) {
        // Walk up parent chain until reaching root
        while (parent[x] != x) x = parent[x];
        return x;
    }

    public boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false; // already same set
        parent[rx] = ry; // attach root of x's tree to root of y's tree
        return true;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

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.

public class DisjointSetWithRank {
    private int[] parent;
    private int[] rank;

    public DisjointSetWithRank(int n) {
        parent = new int[n];
        rank = new int[n]; // default 0
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int find(int x) {
        while (parent[x] != x) x = parent[x];
        return x;
    }

    public boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        // Attach smaller-rank tree under larger-rank tree
        if (rank[rx] < rank[ry]) { int tmp = rx; rx = ry; ry = tmp; }
        parent[ry] = rx;
        if (rank[rx] == rank[ry]) rank[rx]++;
        return true;
    }
}

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.

public int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // compress on the way back
    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.

public int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]]; // path halving -- skip one level
        x = parent[x];
    }
    return x;
}

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

Kết hợp cả hai optimization:

public class DisjointSetUnion {
    private int[] parent;
    private int[] rank;

    public DisjointSetUnion(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    // Full path compression -- recursive
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    // Union by rank -- attach smaller tree under larger tree
    public boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) { int tmp = rx; rx = ry; ry = tmp; }
        parent[ry] = rx;
        if (rank[rx] == rank[ry]) rank[rx]++;
        return true;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

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].

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 — 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).

// WRONG: only union by rank, no path compression
public int find(int x) {
    while (parent[x] != x) x = parent[x]; // O(log n) per call -- not optimal
    return x;
}

// WRONG: only path compression, no union by rank
public boolean union(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return false;
    parent[rx] = ry; // no rank check -- tree can still become tall before compression
    return true;
}

Phải dùng cả hai để đạt O(α(n)). Trên 1 triệu operation: chênh lệch thực tế 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 StackOverflowError trong Java (default stack ~512 frame).

// RISKY for large chains before first compression:
public int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // recursion depth = tree height
    return parent[x];
}

Giải pháp: dùng iterative two-pass hoặc path halving.

// SAFE: iterative two-pass full compression
public int find(int x) {
    int root = x;
    while (parent[root] != root) root = parent[root]; // pass 1: find root
    while (parent[x] != root) {                        // pass 2: compress
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

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 -- two threads calling union concurrently:
// Thread A: find(x) reads parent[x] = 3
// Thread B: find(x) writes parent[x] = 1 (path compression)
// Thread A: writes parent[x] = 5 (old stale value)
// Result: parent[x] no longer points to root -- find() loops or returns wrong root

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 synchronized 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: size of set containing x
public int size(int x) {
    return size[find(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 (e.g. 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.

Link-cut tree: tổng quát hóa DSU cho phép union/find trên cây động với O(log n) amortized — Module 5 extension nâng cao.

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)
//   reads: parent[5] = 3
//   reads: parent[3] = 1 -> root = 1
//   writes: parent[5] = 1  (path compress)

// Thread B: concurrently -- find(3)
//   reads: parent[3] = 1 -> root = 1
//   union(3, 7): writes parent[1] = 7 (new root)

// Now Thread A writes parent[5] = 1 (stale root!)
// parent[1] = 7 but parent[5] = 1 -- find(5) returns 1, not 7 -> WRONG

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