Disjoint set: bài toán distinct subsets và cài đặt naive

Giới thiệu

Bài này học disjoint set để gom nhóm và hỏi cùng nhóm. Cấu trúc này giúp gộp cộng đồng nhanh và gọn.

Kiến thức cần nhớ

Bài toán gom nhóm

• Mỗi phần tử thuộc đúng một nhóm tại mỗi thời điểm.
• Cần hỏi hai người có cùng nhóm không.
• Cần gộp hai nhóm thành một khi kết bạn.
• Ví dụ đời thường: gộp hai nhóm chat thành một nhóm.

API ba thao tác

• makeSet(x): tạo nhóm riêng chỉ chứa x.
• find(x): trả về đại diện nhóm của x.
• union(a, b): gộp nhóm của a và b.
• Ví dụ đời thường: hỏi cùng lớp, rồi chuyển hai bạn về chung lớp.

Cài đặt ngây thơ

• Mỗi phần tử lưu trực tiếp id nhóm trong dict.
• find chỉ đọc dict nên rất nhanh $O(1)$.
• union phải duyệt viết lại id cả nhóm nên $O(n)$.
• Ví dụ đời thường: đổi tên lớp phải sửa thẻ từng học sinh.

# Cài đặt ngây thơ: find nhanh, union chậm
parent = {}  # mỗi người -> id nhóm
def find(x):
    return parent[x]  # đọc trực tiếp
def union(a, b):
    ida, idb = parent[a], parent[b]  # lấy 2 id
    if ida == idb: return False  # đã cùng nhóm
    for k in parent:  # duyệt hết để viết lại
        if parent[k] == idb:
            parent[k] = ida
    return True

Ví dụ

• Input: 5 người riêng lẻ, hỏi 1 và 2 -> Output: khác nhóm.
• Câu này cho thấy lúc đầu ai cũng một mình.
• Input: union(1,2) rồi hỏi 1 và 2 -> Output: cùng nhóm, trả True.
• Câu này cho thấy gộp xong thì hỏi ra cùng nhóm.

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-032/. Phần tử là số nguyên 0..n-1.

Bài 1: Disjoint set ngây thơ (quick-find)

class QuickFind {
 public:
  explicit QuickFind(int n);           // makeSet cho 0..n-1
  int  find(int x) const;              // O(1)
  bool unite(int a, int b);            // O(n), trả false nếu đã cùng nhóm
  bool connected(int a, int b) const;
  int  count() const;                  // số nhóm hiện tại
};

n=5                           -> count = 5, connected(1,2) = false
unite(1,2); unite(3,4)        -> count = 3
unite(2,1)                    -> false (đã cùng nhóm)
unite(1,4)                    -> connected(2,3) = true, count = 2
find(9)                       -> ném out_of_range

Bài 2: Quick-union không tối ưu

Viết QuickUnion lưu mảng parent. find đi lên tới gốc. unite nối gốc của a vào gốc của b.

Tạo dãy thao tác xấu: unite(0,1), unite(1,2), ..., unite(n-2, n-1) rồi gọi find(0). Đếm số bước find đi. In độ cao cây.

Bài 3: Bài toán mạng bạn bè (nâng cao)

Đọc file friends.txt, mỗi dòng a b là quan hệ bạn bè:

1. In số nhóm bạn bè (thành phần liên thông).
2. In kích thước nhóm lớn nhất.
3. Trả lời truy vấn a b: có cùng nhóm không.
4. Sinh $n = 10^4$ người, $10^4$ cạnh ngẫu nhiên. Đo thời gian QuickFind và QuickUnion. Ghi kết quả để so với bản tối ưu ngày 33.

friends: 0-1, 1-2, 3-4
-> 3 nhóm với n=6 ({0,1,2}, {3,4}, {5}), nhóm lớn nhất 3

✅ Tiêu chí hoàn thành

• Test mẫu pass cho cả QuickFind và QuickUnion.
• Bài 2 cho thấy độ cao cây bằng n - 1 với dãy xấu.
• Bảng thời gian Bài 3 có số thật.
• Nêu được độ phức tạp find và unite của 2 cách cài.

❓ Câu hỏi ôn tập

• Bài toán gom nhóm cần hỏi gì và gộp gì?
• API disjoint set gồm 3 thao tác nào?
• Vì sao cài đặt ngây thơ gộp rất chậm?
• Khi nào hai phần tử được coi cùng nhóm?

🌕 Bạn đã hoàn thành ngày 32. Làm hết bài tập phía trên rồi sang ngày tiếp theo.