Chuyển tới nội dung chính

Union-Find (Disjoint Set Union)

Bạn sẽ học được gì

Union-Find (còn gọi DSU — Disjoint Set Union, tập rời nhau) trả lời cực nhanh hai câu hỏi: "hai phần tử có cùng nhóm không?" và "gộp hai nhóm lại". Với hai tối ưu nén đường (path compression) và hợp theo hạng (union by rank), mỗi thao tác gần như O(1) khấu hao. Đây là cấu trúc đứng sau Kruskal.

1. Trực quan: ai cùng băng nhóm?​

Hình dung một sân chơi đông trẻ, dần dần kết bạn thành các nhóm. Bạn cần biết nhanh: "hai bạn này cùng nhóm chưa?" và "nhập hai nhóm lại làm một". Mỗi nhóm chọn một bạn làm trưởng nhóm (đại diện). Hỏi "cùng nhóm?" = "hai bạn có cùng trưởng nhóm không?".

   Moi nhom la mot cay, goc = dai dien:

        1            4
       / \           |
      2   3          5

   nhom A = {1,2,3} (dai dien 1)
   nhom B = {4,5}   (dai dien 4)

   find(3) leo len goc -> 1
   find(5) -> 4   => 3 va 5 KHAC nhom

2. Hai thao tác cốt lõi​

Thao tácÝ nghĩa
find(x)tìm đại diện (gốc) của nhóm chứa x
union(a, b)gộp nhóm của a và nhóm của b

Cài đặt cơ bản: mảng parent, ban đầu mỗi phần tử là cha của chính nó (mỗi người một nhóm riêng). find leo theo parent tới khi gặp gốc (phần tử có parent[x] == x).

3. Chạy debug: union rồi find​

🐞 parent = [0,1,2,3,4], union(0,1), union(2,3), union(1,2)Bước 1/6
1parent = [0, 1, 2, 3, 4]
2def find(x):
3  while parent[x] != x:
4      x = parent[x]
5  return x
6def union(a, b):
7  parent[find(a)] = find(b)
8union(0, 1)
9union(2, 3)
10union(1, 2)
Biến tại bước này
parent[0,1,2,3,4]
👉 Mỗi phần tử là một nhóm riêng.

4. Code chạy được (đầy đủ tối ưu)​

Đang tải trình chạy code…

5. Hai tối ưu làm nên tốc độ​

Nén đường (path compression): mỗi lần find, kéo các node trên đường về sát gốc, làm cây phẳng dần — lần hỏi sau nhanh hơn.

Hợp theo hạng (union by rank): khi gộp, luôn treo cây thấp vào cây cao để cây không bị dài ra. Kết hợp cả hai, mỗi thao tác chỉ tốn O(α(n)) — với α là hàm Ackermann ngược, gần như là hằng số (≤ 4 với mọi n thực tế).

   Truoc nen:        Sau khi find(4):
      1                    1
      |                  / | \
      2                 2  3  4
      |
      3
      |
      4

6. Phân tích & ứng dụng​

Thao tácĐộ phức tạp (có 2 tối ưu)
findgần O(1) khấu hao — O(α(n))
uniongần O(1) khấu hao

Ứng dụng:

  • Kruskal: kiểm tra cạnh có tạo chu trình không.
  • Đếm số thành phần liên thông khi thêm cạnh dần.
  • Kiểm tra hai phần tử "cùng nhóm" trong các bài gom cụm, mạng xã hội.

Bẫy thường gặp: quên một trong hai tối ưu → cây có thể suy biến thành chuỗi dài, find tụt về O(n).

7. Mẫu nhận diện​

  • "Gộp nhóm", "cùng một tập / cùng kết nối?", "thành phần liên thông động" → Union-Find.
  • "Thêm cạnh dần và hỏi số cụm" → DSU cập nhật nhanh hơn chạy lại DFS mỗi lần.
  • Là bước phụ trong Kruskal và nhiều bài đồ thị offline.

8. 🎮 Trò chơi: Hiểu Union-Find​

🎮 Hiểu Union-Find (DSU)Câu 1/4· Điểm 0· 🔥 0

find tìm đại diện nhóm; union gộp hai nhóm. Hai tối ưu cho gần O(1).

Hai tối ưu giúp DSU đạt gần O(1) là?

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. DSU quản lý loại dữ liệu nào?
2. Với nén đường + hợp theo hạng, mỗi thao tác find/union tốn?
3. Hai phần tử "cùng nhóm" khi nào?

10. Hoàn thành​

…

☑️ Tiếp theo: 3.4.1 — Quy hoạch động: DP là gì (nhớ lại kết quả con để giải bài lớn).