Disjoint Set Union (DSU)

DSU (Disjoint Set Union), còn gọi là Union-Find hay cấu trúc các tập rời nhau, quản lý một họ các tập hợp không giao nhau và cho phép trả lời nhanh hai câu hỏi: "hai phần tử có đang ở cùng một tập không?" và "gộp hai tập làm một". Với hai tối ưu chuẩn (nén đường đi + gộp theo hạng), mỗi thao tác chỉ tốn $O(\alpha (N))$ — gần như $O(1)$ — thay vì $O(N)$ nếu duyệt lại toàn bộ. Đây là công cụ nền tảng cho thuật toán Kruskal, đếm thành phần liên thông, và vô số bài xử lý offline trên đồ thị.

Ý tưởng / Trực giác

Mỗi tập hợp được biểu diễn bằng một cây có gốc: mọi phần tử trỏ tới cha của nó, và gốc cây chính là đại diện (representative) của cả tập. Hai phần tử thuộc cùng một tập khi và chỉ khi chúng leo lên tới cùng một gốc.

• Find(x): đi từ $x$ theo các con trỏ cha cho tới khi gặp gốc (phần tử tự trỏ vào chính nó). Gốc đó định danh tập chứa $x$.
• Union(x, y): tìm gốc của $x$ và của $y$; nếu khác nhau, cho gốc này trỏ vào gốc kia — hai cây nhập thành một.

Nếu chỉ làm vậy, cây có thể thoái hóa thành một chuỗi dài và Find tốn $O(N)$. Hai tối ưu sau giữ cây luôn "lùn":

1. Gộp theo hạng / kích thước (union by size/rank): khi gộp, luôn treo cây nhỏ hơn vào dưới gốc cây lớn hơn. Nhờ đó độ cao cây tăng rất chậm — một phần tử chỉ bị "tụt sâu thêm" khi cây của nó bị treo vào một cây ít nhất to gấp đôi, nên độ sâu tối đa là $O(\log N)$.

2. Nén đường đi (path compression): trong lúc Find, sau khi tìm ra gốc, ta cho mọi đỉnh trên đường đi trỏ thẳng vào gốc. Lần Find sau với các đỉnh đó chỉ còn một bước nhảy.

Vì sao đúng và vì sao nhanh? Tính đúng đến từ việc "cùng tập ⟺ cùng gốc" luôn được bảo toàn: nén đường đi chỉ rút ngắn con trỏ chứ không đổi gốc; gộp theo hạng chỉ chọn gốc nào làm gốc chung. Khi dùng cả hai tối ưu, tổng chi phí cho $M$ thao tác là $O(M\alpha (N))$, với $\alpha$ là hàm ngược Ackermann — nhỏ hơn $5$ với mọi $N$ thực tế (kể cả $N$ lớn hơn số nguyên tử trong vũ trụ). Đó là lý do người ta coi DSU "gần như hằng số".

Ví dụ chạy tay

Khởi tạo $n=6$ phần tử $\{0,1,2,3,4,5\}$, mỗi phần tử là một tập riêng (cha trỏ chính nó), kích thước $=1$.

i:      0   1   2   3   4   5
parent: 0   1   2   3   4   5      (mỗi đỉnh là gốc của chính nó)
size:   1   1   1   1   1   1

Thực hiện lần lượt: union(0,1), union(2,3), union(1,3), union(4,5).

union(0,1): find(0)=0, find(1)=1, khác gốc. Hai cây cùng size, treo 1 dưới 0.

parent: [0] 0   2   3   4   5      (1 -> 0)
size:    2  .   1   1   1   1

   0          2     3     4     5
   |
   1

union(2,3): find(2)=2, find(3)=3. Treo 3 dưới 2.

parent:  0  0  [2] 2   4   5       (3 -> 2)
size:    2  .   2  .   1   1

   0      2       4     5
   |      |
   1      3

union(1,3): find(1) leo $1\to 0$, gốc $=0$; find(3) leo $3\to 2$, gốc $=2$. Hai gốc 0 và 2 cùng size $=2$ → treo 2 dưới 0, size[0] thành 4.

parent: [0] 0   0   2   4   5      (2 -> 0)
size:    4  .   .   .   1   1

      0
     / \
    1   2
        |
        3

union(4,5): treo 5 dưới 4.

      0           4
     / \          |
    1   2         5
        |
        3

Bây giờ kiểm tra connected(1, 3): gọi find(1) → $1\to 0$, gốc 0. find(3) → $3\to 2\to 0$, gốc 0. Nén đường đi: đỉnh 3 (và 2) được trỏ thẳng vào gốc 0:

parent: 0  0  0  0  4  5           (3 nhảy thẳng -> 0)

      0
    / | \
   1  2  3        <- 3 đã được nén lên ngang hàng

Cùng gốc 0 ⇒ connected(1,3) = true. Trong khi connected(1,4): gốc của 1 là 0, gốc của 4 là 4 ⇒ false. Lúc này có đúng 2 thành phần liên thông: $\{0,1,2,3\}$ và $\{4,5\}$.

Cài đặt

C++

struct DSU {
    vector<int> parent, sz;        // sz[r] chỉ có nghĩa khi r là gốc

    DSU(int n) : parent(n), sz(n, 1) {
        iota(parent.begin(), parent.end(), 0);   // parent[i] = i
    }

    // Find có nén đường đi: trỏ thẳng mọi đỉnh trên đường lên gốc
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // gán lại = nén đường đi
        return parent[x];
    }

    // Gộp theo kích thước. Trả về false nếu đã cùng tập (không có gì thay đổi)
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y); // x là gốc cây LỚN hơn
        parent[y] = x;                 // treo cây nhỏ (y) dưới cây lớn (x)
        sz[x] += sz[y];
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }   // số phần tử trong tập chứa x
};

Python

Đệ quy find của Python dễ vượt giới hạn đệ quy với $N$ lớn, nên dùng vòng lặp:

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.sz = [1] * n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:        # nén đường đi (lặp 2 lượt)
            self.parent[x], x = root, self.parent[x]
        return root

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self.sz[x] < self.sz[y]:
            x, y = y, x
        self.parent[y] = x
        self.sz[x] += self.sz[y]
        return True

Độ phức tạp

Vì sao $O(\alpha (N))$? Riêng gộp theo hạng giữ độ cao cây $\le O(\log N)$. Riêng nén đường đi cũng cho biên phân bổ tốt. Khi kết hợp cả hai, tổng chi phí $M$ thao tác là $O(M\alpha (N))$ — chứng minh kinh điển của Tarjan. Vì $\alpha (N)\le 4$ với mọi $N\le {10}^{600}$, trên thực tế mỗi thao tác coi như hằng số. Lưu ý đây là biên phân bổ (amortized): một lần find lẻ có thể tốn tới $O(\log N)$, nhưng trung bình trên cả dãy thì rất nhỏ.

Bộ nhớ: hai mảng parent và sz, mỗi mảng $N$ phần tử, tổng $O(N)$.

⚠️ Lỗi thường gặp

• Quên gọi find trước khi so sánh/gộp. Viết if (parent[x] == parent[y]) hay parent[y] = x với $x,y$ là phần tử thô thay vì gốc là sai. Luôn x = find(x); y = find(y); trước. Triệu chứng: hai phần tử cùng tập bị báo khác tập, hoặc cây bị nối lệch.

• Đánh số 0-based vs 1-based. Đề thường đánh đỉnh từ $1$ đến $N$. Nếu khởi tạo DSU(n) (chỉ số $0..n-1$) mà truy cập đỉnh $N$ thì tràn mảng. Khắc phục: khởi tạo DSU(n + 1) hoặc trừ 1 khi đọc. Triệu chứng: lỗi truy cập ngoài biên / kết quả sai ở đỉnh cuối.

• Bỏ một trong hai tối ưu nhưng tưởng vẫn nhanh. Chỉ union-by-size mà không nén (hoặc ngược lại) cho $O(\log N)$; nếu không có cả hai (luôn treo y dưới x bất kể kích thước), cây có thể thành chuỗi và find tụt xuống $O(N)$ → bài $N$ lớn bị TLE. Đừng "đơn giản hóa" code bằng cách bỏ if (sz[x] < sz[y]) swap.

• Cập nhật sz/dữ liệu phụ ở sai phía sau khi gộp. Sau swap và parent[y]=x, mọi thông tin tổng hợp (kích thước, tổng, số cạnh...) phải cộng vào gốc mới $x$, không phải $y$. Và chỉ đọc sz[r] khi $r$ thật sự là gốc — sz của đỉnh không phải gốc là rác.

• Đọc giá trị qua phần tử thay vì qua gốc. Khi DSU mang thêm thông tin (vd "tổng của tập"), phải truy vấn data[find(x)], không phải data[x]. Quên find ở đây là lỗi rất khó phát hiện vì code vẫn chạy.

• Tràn số khi cộng trọng số. Trong Kruskal hoặc khi DSU cộng dồn trọng số/đếm, dùng long long cho biến tổng nếu tổng có thể vượt $2^{31}$. parent/sz thì int là đủ.

Biến thể / Mở rộng

• DSU theo trọng số (weighted / DSU có nhãn quan hệ): ngoài con trỏ cha, lưu thêm "khoảng cách tới cha" để trả lời quan hệ tương đối giữa các phần tử (vd bài chia phe đối lập, kiểm tra mâu thuẫn ràng buộc $a-b=d$).

• DSU offline + sắp xếp cạnh: rất nhiều bài MST/đồ thị xử lý bằng cách sắp xếp các cạnh theo trọng số rồi gộp dần (Kruskal). Đây là khuôn mẫu của hầu hết bài "tìm $D$ nhỏ nhất để liên thông".

• DSU có rollback / không nén đường đi: khi cần hoàn tác các thao tác gộp (vd DSU trên cây phân đoạn thời gian — offline dynamic connectivity), người ta dùng chỉ union-by-rank, bỏ nén đường đi (vì nén làm hỏng khả năng undo), mỗi thao tác $O(\log N)$.

• Small-to-large: kỹ thuật gộp tập nhỏ vào tập lớn (chính là union-by-size) còn dùng để gộp cấu trúc phụ (set, map) với tổng chi phí $O(N\log N)$.

Bài tập luyện

• Quy hoạch hàng rào (fenceplan) — (Trung cấp) Gộp các điểm theo cạnh rồi tìm thành phần có chu vi bao nhỏ nhất; bài nhập môn DSU với dữ liệu tổng hợp (min/max tọa độ) tại gốc mỗi tập.
• Máy kéo (tractorb) — (Trung cấp) Sắp xếp các cạnh lưới theo hiệu độ cao rồi gộp dần đến khi một thành phần đủ lớn; mẫu Kruskal điển hình kết hợp truy vấn size(find(x)).
• Hầm Ngục Hogwarts (cheese) — (Trung cấp) Nối các buồng cầu giao nhau rồi hỏi đáy và trần có cùng thành phần không; luyện đếm/kiểm tra liên thông bằng connected.
• Đồ thị điều hòa (harmgraph) — (Nâng cao) Dùng DSU để gom thành phần liên thông rồi suy luận trên khoảng chỉ số $[min,max]$ của từng thành phần; DSU làm bước tiền xử lý cho phần greedy.
• Màu yêu thích (favcolor) — (Nâng cao) Hai đỉnh cùng ngưỡng mộ một đỉnh phải cùng màu — đây chính là ràng buộc "phải cùng tập", giải bằng cách gộp DSU lan truyền rồi gán màu theo thứ tự từ điển.