Disjoint Set Union — Quản lý tập hợp rời rạc

Bạn có 10.000 server trong data center. Mỗi phút, một cặp server được nối mạng với nhau. Tại thời điểm bất kỳ, bạn cần trả lời: "Server A và server B có thể liên lạc được không?" — trong O(1). BFS/DFS mỗi lần query tốn O(V+E), quá chậm khi có hàng triệu query. Đây là lúc Disjoint Set Union (DSU) — hay Union-Find — tỏa sáng.

DSU quản lý các tập hợp rời rạc với hai thao tác cốt lõi: Find(x) — tìm đại diện của tập chứa x, và Union(x, y) — hợp nhất hai tập. Với hai tối ưu kinh điển — path compression và union by rank — mỗi thao tác gần như O(1) amortized. Cấu trúc dữ liệu này là nền tảng của Kruskal's MST, dynamic connectivity, và hàng loạt bài toán graph khác.

Bức tranh tư duy

Hình dung Việt Nam thời phong kiến với nhiều làng riêng biệt. Mỗi làng có một trưởng làng (đại diện). Khi hai làng quyết định hợp nhất, làng nhỏ sẽ theo trưởng làng lớn — giữ cây quyền lực cân bằng. Muốn biết hai người có cùng làng không? Cứ hỏi ngược lên trưởng làng — nếu cùng trưởng làng thì cùng làng.

Ban đầu: mỗi người là trưởng của chính mình
  [A]  [B]  [C]  [D]  [E]  [F]

Union(A, B): B theo A          Union(C, D): D theo C
  A          C
  |          |
  B          D

Union(A, C): Cây nhỏ (C) gắn vào cây lớn hơn (A)
      A
    / |
   B  C
      |
      D

Find(D) → A  (leo lên gốc)
Find(B) → A  (cùng gốc → cùng nhóm!)

Path compression: Sau khi Find(D) leo qua C rồi đến A, ta nối thẳng D → A. Lần sau Find(D) chỉ mất 1 bước thay vì 2. Cây ngày càng phẳng sau mỗi lần query.

📌 Khi nào analogy bị phá vỡ

Làng thật có thể tách ra (ly khai). DSU chuẩn chỉ hỗ trợ Union, không hỗ trợ Split. Nếu cần xóa cạnh, phải dùng cấu trúc phức tạp hơn (Link-Cut Tree, offline với DSU rollback).

Cốt lõi kỹ thuật

Cấu trúc cơ bản

Mỗi phần tử trỏ tới parent. Gốc (root/representative) trỏ tới chính nó. Find leo lên gốc, Union nối gốc của hai cây lại.

C++

struct DSU {
    vector<int> parent, rank_;
    int components;

    DSU(int n) : parent(n), rank_(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0);
    }

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

    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank_[px] < rank_[py]) swap(px, py);
        parent[py] = px; // union by rank
        if (rank_[px] == rank_[py]) rank_[px]++;
        components--;
        return true;
    }

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

Python

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n
        self.components = n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x: int, y: int) -> bool:
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        self.size[px] += self.size[py]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.components -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def get_size(self, x: int) -> int:
        return self.size[self.find(x)]

Java

class DSU {
    int[] parent, rank;
    int components;

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

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

    boolean unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        components--;
        return true;
    }

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

Go

type DSU struct {
    parent, rank []int
    Components   int
}

func NewDSU(n int) *DSU {
    p := make([]int, n)
    for i := range p { p[i] = i }
    return &DSU{parent: p, rank: make([]int, n), Components: n}
}

func (d *DSU) Find(x int) int {
    if d.parent[x] != x {
        d.parent[x] = d.Find(d.parent[x])
    }
    return d.parent[x]
}

func (d *DSU) Unite(x, y int) bool {
    px, py := d.Find(x), d.Find(y)
    if px == py { return false }
    if d.rank[px] < d.rank[py] { px, py = py, px }
    d.parent[py] = px
    if d.rank[px] == d.rank[py] { d.rank[px]++ }
    d.Components--
    return true
}

func (d *DSU) Connected(x, y int) bool {
    return d.Find(x) == d.Find(y)
}

Path Compression — làm phẳng cây

Mỗi lần find(x), ta nối thẳng x về root. Tất cả node trên đường đi đều được nối thẳng — cây trở nên cực kỳ phẳng sau vài thao tác.

Trước find(D):      Sau find(D):
    A                   A
    |                 / | \
    B               B   C   D
    |
    C
    |
    D

Union by Rank — giữ cây cân bằng

Luôn gắn cây thấp hơn vào cây cao hơn. Rank là upper bound của chiều cao. Nếu hai cây cùng rank, rank tăng 1. Điều này đảm bảo chiều cao cây tối đa O(log n) ngay cả khi chưa có path compression.

Kết hợp hai tối ưu

Path compression + union by rank cho amortized complexity O(α(n)) mỗi thao tác — với α là hàm Ackermann nghịch đảo. Trong thực tế, α(n) ≤ 4 cho mọi n ≤ 10^{80} (số atom trong vũ trụ). Coi như O(1).

Thực chiến

Tình huống 1: Kiểm tra connectivity động

Bối cảnh: Hệ thống mạng thêm kết nối dần, cần kiểm tra hai node có liên lạc được không sau mỗi lần thêm.

def process_network_events(
    n: int,
    events: list[tuple[str, int, int]]
) -> list[bool]:
    dsu = DSU(n)
    results = []
    for action, u, v in events:
        if action == "connect":
            dsu.unite(u, v)
        elif action == "query":
            results.append(dsu.connected(u, v))
    return results

# 100K events xử lý gần như tức thì

Phân tích: Mỗi event O(α(n)) ≈ O(1). Tổng M events: O(M × α(n)). Với BFS/DFS, mỗi query O(V+E) — chậm hơn hàng nghìn lần.

Tình huống 2: Đếm connected components

Bối cảnh: Social network — đếm số nhóm bạn bè riêng biệt.

def count_friend_groups(n: int, friendships: list[tuple[int, int]]) -> int:
    dsu = DSU(n)
    for u, v in friendships:
        dsu.unite(u, v)
    return dsu.components

Sai lầm điển hình

❌ Sai lầm 1: Quên path compression

Vấn đề: Chỉ dùng union by rank mà không path compression.

# SAI: find không flatten
def find(self, x):
    while self.parent[x] != x:
        x = self.parent[x]
    return x

Tại sao sai: Không có path compression, worst case vẫn O(log n) mỗi find. Với path compression, giảm xuống O(α(n)). Trên 10 triệu thao tác, sự khác biệt là đáng kể.

# ĐÚNG: path compression — nối thẳng về root
def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])
    return self.parent[x]

❌ Sai lầm 2: Union không kiểm tra cùng tập

Vấn đề: Không kiểm tra px == py trước khi union.

# SAI: rank/size bị sai nếu hai node đã cùng tập
def unite(self, x, y):
    px, py = self.find(x), self.find(y)
    self.parent[py] = px
    self.size[px] += self.size[py]  # cộng sai nếu px == py!
    self.components -= 1             # trừ sai!

Tại sao sai: Nếu x, y đã cùng tập, size bị cộng đôi và components bị trừ thừa. Production bug khó phát hiện — size sai dẫn đến các tính toán downstream sai theo.

# ĐÚNG: kiểm tra trước khi union
def unite(self, x, y):
    px, py = self.find(x), self.find(y)
    if px == py:
        return False
    # ... proceed with union

❌ Sai lầm 3: Dùng DSU cho directed graph

Vấn đề: DSU chỉ xử lý undirected connectivity.

# SAI: "A → B" không có nghĩa "B → A" trong directed graph
for u, v in directed_edges:
    dsu.unite(u, v)  # coi như undirected!

Tại sao sai: DSU merge hai tập thành một — mất thông tin về hướng cạnh. Cho directed graph, dùng Tarjan's SCC hoặc Kosaraju.

# ĐÚNG: dùng SCC cho directed connectivity
# DSU chỉ dùng cho undirected graph

Under the Hood

Hiệu năng

Thao tác	Naive (no optimization)	Path Compression only	Union by Rank only	Cả hai
Find	O(n)	O(log n) amortized	O(log n)	O(α(n))
Union	O(n)	O(log n) amortized	O(log n)	O(α(n))
M thao tác trên N phần tử	O(M × N)	O(M × log N)	O(M × log N)	O(M × α(N))

Hàm Ackermann nghịch đảo α(n)

α(n) là hàm ngược của hàm Ackermann — một hàm tăng cực nhanh. α(n) tăng cực chậm:

n	α(n)
1	0
2-3	1
4-7	2
8-2047	3
2048 đến 10^	4

Trong thực tế, α(n) không bao giờ vượt 4. Đây là lý do DSU được coi là O(1) per operation.

Trade-offs

Khi nào dùng DSU	Khi nào KHÔNG dùng
Dynamic connectivity (thêm cạnh)	Cần xóa cạnh (dùng Link-Cut Tree)
Kruskal's MST	Directed graph connectivity (dùng SCC)
Undirected cycle detection	Cần liệt kê path giữa hai node
Đếm/quản lý connected components	Static graph (BFS/DFS đủ tốt)

Checklist ghi nhớ

✅ Checklist triển khai

Cài đặt chuẩn

• [ ] Path compression trong find: parent[x] = find(parent[x])
• [ ] Union by rank: cây thấp gắn vào cây cao
• [ ] Kiểm tra find(x) == find(y) trước khi union — tránh cộng sai size/components
• [ ] Khởi tạo: parent[i] = i, rank[i] = 0

Ứng dụng

• [ ] Kruskal's MST: sort edges + DSU để kiểm tra cycle
• [ ] Dynamic connectivity: thêm cạnh → union, query → connected
• [ ] Đếm connected components: components giảm 1 sau mỗi union thành công

Giới hạn

• [ ] Chỉ dùng cho undirected graph
• [ ] Không hỗ trợ delete/split (chuẩn)
• [ ] Amortized O(α(n)) — không phải worst-case O(1) cho từng thao tác đơn lẻ

Bài tập luyện tập

Bài 1: Number of Connected Components — Foundation

Đề bài: Cho n node (0 đến n-1) và danh sách cạnh undirected. Đếm số connected components. (LeetCode 323)

🧠 Quiz

Sau khi thực hiện path compression trên find(x), điều gì xảy ra với cây?

• [ ] A. Cây bị xóa hoàn toàn
• [ ] B. Chỉ node x được nối về root
• [x] C. Tất cả node trên đường từ x đến root đều được nối thẳng về root
• [ ] D. Rank của root tăng lên Giải thích: Path compression (recursive) nối mọi node trên đường đi về root. Rank không đổi — rank là upper bound, không phải chiều cao chính xác.

💡 Gợi ý

• Khởi tạo DSU với n phần tử
• Union tất cả cạnh
• Trả về dsu.components

✅ Lời giải

def countComponents(n: int, edges: list[list[int]]) -> int:
    dsu = DSU(n)
    for u, v in edges:
        dsu.unite(u, v)
    return dsu.components

Phân tích: O(E × α(N)) ≈ O(E) time, O(N) space.

Bài 2: Redundant Connection — Intermediate

Đề bài: Cho cây n node bị thêm 1 cạnh thừa (tạo cycle). Tìm cạnh thừa đó. Nếu nhiều đáp án, trả về cạnh cuối cùng trong input. (LeetCode 684)

💡 Gợi ý

• Duyệt cạnh theo thứ tự input
• Cạnh mà union thất bại (hai đỉnh đã cùng component) chính là cạnh thừa

✅ Lời giải

def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
    dsu = DSU(n + 1)
    for u, v in edges:
        if not dsu.unite(u, v):
            return [u, v]
    return []

Phân tích: O(N × α(N)) time. Trick: cạnh tạo cycle = cạnh mà hai đỉnh đã connected.

Liên kết học tiếp

📚 Bài liên quan

Bài liên quan trong Penalgo

• ← Topological Sort — sắp xếp phụ thuộc trên DAG
• → Minimum Spanning Tree — Kruskal's MST dùng DSU làm nền tảng
• BFS & DFS — duyệt đồ thị cơ bản, alternative cho static connectivity
• Dijkstra — shortest path, bài toán graph liên quan

Từ khóa glossary: DSU, Union-Find, path compression, union by rank, inverse Ackermann, tập hợp rời rạc

Tìm kiếm liên quan: quản lý tập hợp, kiểm tra kết nối, connected components, cycle detection undirected