7. Disjoint Set (Union-Find)
7.1. Union-Find là gì?
Ví dụ thực tế: Mạng xã hội — mỗi người là 1 node. Khi hai người kết bạn, họ thuộc cùng “nhóm”. Bạn cần trả lời nhanh: “A và B có cùng nhóm bạn không?” và “Gộp nhóm của A và nhóm của B lại”.
Union-Find (hay Disjoint Set Union - DSU) hỗ trợ 2 thao tác:
- Find(x): Tìm đại diện (root/leader) của nhóm chứa x
- Union(x, y): Gộp nhóm chứa x và nhóm chứa y thành 1 nhóm
7.2. Naive Implementation
class UnionFindNaive:
"""Union-Find cơ bản — chưa tối ưu."""
def __init__(self, n):
# Ban đầu mỗi phần tử là root của chính nó
self.parent = list(range(n))
def find(self, x):
"""Tìm root của x — đi ngược lên cây cho đến gốc."""
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
"""Gộp nhóm chứa x và nhóm chứa y."""
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y # Gắn root_x dưới root_y
def connected(self, x, y):
"""Kiểm tra x và y có cùng nhóm không."""
return self.find(x) == self.find(y)Vấn đề: Cây có thể trở nên rất cao (worst case: thành linked list) → Find mất O(n).
7.3. Path Compression
Ý tưởng: Khi gọi find(x), trên đường đi từ x lên root, trỏ thẳng tất cả node lên root. Lần find sau sẽ nhanh hơn.
Ví dụ: Trước: 5 → 4 → 3 → 2 → 1 (root). Sau find(5): 5 → 1, 4 → 1, 3 → 1, 2 → 1. Tất cả đều trỏ thẳng lên root!
def find_with_path_compression(self, x):
"""Find với path compression — đệ quy."""
if self.parent[x] != x:
self.parent[x] = self.find_with_path_compression(self.parent[x])
return self.parent[x]7.4. Union by Rank
Ý tưởng: Khi gộp hai cây, luôn gắn cây THẤP hơn dưới cây CAO hơn. Giúp cây không bị cao quá.
Rank ở đây là upper bound của chiều cao cây. Ban đầu rank = 0. Khi gộp hai cây cùng rank → rank tăng 1.
7.5. Full Implementation (Tối ưu hoàn chỉnh)
class UnionFind:
"""
Union-Find tối ưu với Path Compression + Union by Rank.
Amortized time per operation: O(α(n)) ≈ O(1)
α(n) là Inverse Ackermann function — tăng cực kỳ chậm,
với mọi n thực tế (n < 10^80), α(n) ≤ 4.
"""
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [1] * n # Kích thước mỗi nhóm
self.num_components = n # Số nhóm hiện tại
def find(self, x):
"""
Tìm root của x với path compression.
Mọi node trên đường đi sẽ trỏ thẳng lên root.
"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""
Gộp nhóm chứa x và nhóm chứa y (union by rank).
Returns True nếu gộp thành công, False nếu đã cùng nhóm.
"""
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # Đã cùng nhóm
# Union by rank: cây thấp gắn vào cây cao
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_y] = root_x
self.size[root_x] += self.size[root_y]
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
self.num_components -= 1
return True
def connected(self, x, y):
"""Kiểm tra x, y cùng nhóm?"""
return self.find(x) == self.find(y)
def get_size(self, x):
"""Lấy kích thước nhóm chứa x."""
return self.size[self.find(x)]
def get_num_components(self):
"""Số nhóm hiện tại."""
return self.num_components
# === TEST: Mô phỏng mạng xã hội ===
if __name__ == "__main__":
# 8 người: 0, 1, 2, ..., 7
uf = UnionFind(8)
# Kết bạn
friendships = [
(0, 1), (1, 2), # Nhóm 1: 0-1-2
(3, 4), # Nhóm 2: 3-4
(5, 6), (6, 7), # Nhóm 3: 5-6-7
]
print("=== Mạng xã hội với Union-Find ===")
for u, v in friendships:
uf.union(u, v)
print(f"Kết bạn {u}-{v} → {uf.get_num_components()} nhóm")
print(f"
0 và 2 cùng nhóm? {uf.connected(0, 2)}") # True
print(f"0 và 3 cùng nhóm? {uf.connected(0, 3)}") # False
print(f"5 và 7 cùng nhóm? {uf.connected(5, 7)}") # True
print(f"Kích thước nhóm của 0: {uf.get_size(0)}") # 3
# Gộp nhóm 1 và nhóm 2
print(f"
Kết bạn 2-3 (gộp hai nhóm):")
uf.union(2, 3)
print(f"0 và 4 cùng nhóm? {uf.connected(0, 4)}") # True
print(f"Số nhóm: {uf.get_num_components()}") # 2
print(f"Kích thước nhóm mới: {uf.get_size(0)}") # 5Output:
=== Mạng xã hội với Union-Find ===
Kết bạn 0-1 → 7 nhóm
Kết bạn 1-2 → 6 nhóm
Kết bạn 3-4 → 5 nhóm
Kết bạn 5-6 → 4 nhóm
Kết bạn 6-7 → 3 nhóm
0 và 2 cùng nhóm? True
0 và 3 cùng nhóm? False
5 và 7 cùng nhóm? True
Kích thước nhóm của 0: 3
Kết bạn 2-3 (gộp hai nhóm):
0 và 4 cùng nhóm? True
Số nhóm: 2
Kích thước nhóm mới: 5
7.6. Phân tích Complexity
| Thao tác | Naive | Path Compression | Union by Rank | Cả hai |
|---|---|---|---|---|
| Find | O(n) worst | O(log n) amortized | O(log n) | O(α(n)) ≈ O(1) |
| Union | O(n) | O(log n) amortized | O(log n) | O(α(n)) ≈ O(1) |
| Space | O(n) | O(n) | O(n) | O(n) |
Inverse Ackermann Function α(n): Hàm nghịch đảo của hàm Ackermann — tăng cực kỳ chậm. Với n = số nguyên tử trong vũ trụ quan sát được (~10^80), α(n) chỉ bằng 4. Nên trong thực tế, O(α(n)) coi như O(1).
Chứng minh Union by Rank giữ chiều cao O(log n):
Bổ đề: Cây có rank r chứa ít nhất 2^r node.
- Base: rank 0 → 1 = 2^0 node. Đúng.
- Inductive: Rank tăng từ r lên r+1 chỉ khi gộp hai cây rank r. Mỗi cây ≥ 2^r node → tổng ≥ 2 × 2^r = 2^(r+1). Đúng.
Hệ quả: n node → rank ≤ log₂(n) → Find mất O(log n) khi chỉ dùng union by rank.
7.7. Ứng dụng Union-Find
- Kruskal’s MST — kiểm tra cycle khi thêm cạnh
- Connected Components — đếm số thành phần liên thông
- Cycle Detection — trong undirected graph
- Network Connectivity — kiểm tra 2 máy có liên thông không
- Image Processing — gộp pixel cùng vùng
- Percolation — mô phỏng thẩm thấu (bài tập kinh điển Princeton)
🔬 Deep Diagnostic & Production Engineering Notes
1. In-Depth State Verification & Invariant Proofs
When deploying algorithms in high-throughput production environments:
- Loop Invariants: State preconditions must be strictly asserted before entering loops. Post-conditions guarantee deterministic state convergence.
- Memory Boundary Defense: Guard against off-by-one errors ( vs ), signed integer overflow (), and empty container operations.
- Asymptotic Amortization: Use aggregate analysis and potential functions to ensure operations maintain their promised average and worst-case bounds.
2. High-Performance Multi-Language Testing Harness
C++20 Micro-Benchmarking Suite
#include <iostream>
#include <vector>
#include <chrono>
#include <numeric>
void BenchmarkSuite(int iterations) {
auto start = std::chrono::high_resolution_clock::now();
long long checksum = 0;
for (int i = 1; i <= iterations; ++i) {
checksum += (i ^ (i << 1));
}
auto end = std::chrono::high_resolution_clock::now();
auto dur = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
std::cout << "Executed " << iterations << " iterations in " << dur << " us. Checksum: " << checksum << "\n";
}Python 3.12 Verification Harness
import time
def verify_performance(iterations: int) -> int:
t0 = time.perf_counter_ns()
checksum = sum(i ^ (i << 1) for i in range(1, iterations + 1))
t1 = time.perf_counter_ns()
print(f"Verified {iterations} iterations in {(t1 - t0) / 1_000_000:.3f} ms. Checksum: {checksum}")
return checksumC# (.NET 8) Memory Profiling Harness
using System;
using System.Diagnostics;
public class BenchmarkRunner {
public static void Run(int iterations) {
long memoryBefore = GC.GetTotalMemory(true);
var sw = Stopwatch.StartNew();
long checksum = 0;
for (int i = 1; i <= iterations; i++) {
checksum += (i ^ (i << 1));
}
sw.Stop();
long memoryAfter = GC.GetTotalMemory(false);
Console.WriteLine($"[C# .NET 8] {iterations} iterations completed in {sw.ElapsedMilliseconds} ms. Memory delta: {memoryAfter - memoryBefore} bytes.");
}
}🔗 Graph-Linked Knowledge Base
- 📖 Subcategory Hub: 12_Graphs Overview