Cấu trúc disjoint-set (union-find) với path compression và union by rank là gì?

Question

Accepted Answer

**Disjoint-set** (union-find) theo dõi các phần tử được phân hoạch thành các nhóm không chồng lấn và trả lời "**hai cái này có cùng nhóm không?**" và "**hợp nhất hai nhóm**" trong **gần thời gian hằng số**. Với **path compression** (nén đường đi) và **union by rank** (hợp theo hạng), cả hai thao tác chạy trong **O(α(n))** — về thực chất là O(1) (α là hàm Ackermann ngược).

## Cách hoạt động

Mỗi tập là một cây; **root** là đại diện của tập. `find` đi tới root; `union` nối một root dưới một root khác.

```text
find(x): đi theo cha tới root
union(a,b): gắn cây thấp hơn dưới cây cao hơn (theo rank)
path compression: sau find, trỏ các node TRỰC TIẾP tới root
   trước:  a->b->c->root      sau:  a->root, b->root, c->root
```

## Code

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):                       # path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # rút ngắn nửa đường đi
            x = self.parent[x]
        return x
    def union(self, a, b):                   # union by rank
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True
```

| Thao tác | Thời gian (với cả hai tối ưu) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |

## Các ứng dụng phổ biến

- **MST của Kruskal** — hợp nhất các thành phần mà không tạo chu trình.
- **Connected components** (thành phần liên thông) trong một graph hoặc lưới.
- **Dynamic connectivity** và các bài toán mạng/percolation.

## Tại sao điều này quan trọng

Union-find giải các bài toán nhóm và liên thông mà nếu không sẽ cần các phép duyệt graph O(n) lặp đi lặp lại, gói gọn chúng về gần O(1) mỗi truy vấn.

Nó là công cụ ưu tiên bất cứ khi nào bạn phải hợp nhất các tập một cách tăng dần và kiểm tra liên thông — một chủ đề phỏng vấn cấp senior thường gặp.