BẢN V2 - Có đồ thị trực quan và giải thích code

🔗 DSU / Union-Find: Quản lý nhóm liên thông

File này đã được nâng cấp rõ ràng: có đồ thị trực quan, mô phỏng parent[], giải thích từng phần code, đặc biệt làm rõ vì sao phải nén path và vì sao cần swap(a,b) khi dùng union by size.

Graph viewĐỉnh, cạnh, component
parent[]Bảng cha cập nhật từng bước
Path compressionRút ngắn đường lên root
swap(a,b)Cây nhỏ treo vào cây lớn
Mục tiêuĐồ thị trực quanparent[]Code DSUGiải thích codeVì sao nén path?Vì sao swap?Bài tậpQuiz

Mục tiêu bài DSU

Học xong cần hiểu

  • DSU quản lý các tập hợp rời nhau, rất hợp với đồ thị vô hướng.
  • find(x) trả về đại diện/root của nhóm chứa x.
  • unite(a,b) nối hai component nếu chúng khác nhau.
  • parent[] không nhất thiết là cạnh đồ thị gốc, mà là cấu trúc nội bộ của DSU.

Hai tối ưu bắt buộc

  • Path compression: sau khi tìm root, kéo các đỉnh trên đường đi trỏ thẳng về root.
  • Union by size/rank: gộp cây nhỏ vào cây lớn để chiều cao cây nhỏ.
  • Hai tối ưu này giúp DSU gần như O(1) cho mỗi thao tác trong thực tế.

1. Đồ thị trực quan: mỗi cạnh là một thao tác unite

Trong đồ thị vô hướng, khi đọc cạnh (u, v), DSU sẽ gộp component chứa u và component chứa v. Cạnh đang xét có màu đỏ, cạnh đã xử lý có màu xanh, các đỉnh cùng component có cùng màu.

Nhấn “Xử lý cạnh tiếp” để bắt đầu.

2. Trạng thái DSU: parent[], size[] và component

Các đỉnh theo component

Bảng parent[]

Bảng parent[] sẽ cập nhật đồng bộ với đồ thị.
Lưu ý quan trọng: parent[x] trong DSU không phải cha của x trong đồ thị gốc. Nó chỉ là mảng nội bộ để biết x thuộc nhóm nào.

3. Code DSU chuẩn

#include 
using namespace std;

struct DSU {
    vector parent, sz;

    DSU(int n) {
        parent.resize(n + 1);
        sz.assign(n + 1, 1);
        iota(parent.begin(), parent.end(), 0);
    }

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

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;

        if (sz[a] < sz[b]) swap(a, b);     // union by size
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }

    bool same(int a, int b) {
        return find(a) == find(b);
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    DSU dsu(n);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        dsu.unite(u, v);
    }

    int components = 0;
    for (int i = 1; i <= n; i++) {
        if (dsu.find(i) == i) components++;
    }
    cout << components;
}
class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        if x == self.parent[x]:
            return x
        self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return False

        if self.size[a] < self.size[b]:
            a, b = b, a       # union by size

        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

    def same(self, a, b):
        return self.find(a) == self.find(b)

4. Giải thích code từng khối

Dòng / khối codeÝ nghĩaLý do cần có
parent[i] = iBan đầu mỗi đỉnh là một nhóm riêng, tự làm root của chính nó.Nếu chưa có cạnh nào, đồ thị có n component.
sz[i] = 1Kích thước component của root i ban đầu là 1.Dùng để biết cây nào nhỏ, cây nào lớn khi gộp.
a = find(a); b = find(b);Chuyển từ đỉnh thường sang root đại diện nhóm.Phải gộp root với root, không gộp tùy tiện hai đỉnh.
if (a == b) return false;Nếu hai đỉnh đã cùng nhóm, không cần nối nữa.Trong Kruskal, điều này còn giúp phát hiện cạnh tạo chu trình.
if (sz[a] < sz[b]) swap(a,b);Đảm bảo a là root của component lớn hơn hoặc bằng.Để treo cây nhỏ vào cây lớn, giúp cây DSU không bị cao.
parent[b] = a;Root b trỏ sang root a, tức hai nhóm đã gộp.Đây là thao tác nối chính của DSU.
sz[a] += sz[b];Cập nhật kích thước nhóm mới.Sau khi gộp, root a đại diện cho cả hai nhóm.

5. Vì sao phải nén path?

Nếu không nén path, một cây DSU có thể trở thành chuỗi dài. Khi đó find(x) phải đi qua nhiều đỉnh mới tới root. Path compression biến đường dài thành đường ngắn bằng dòng:

parent[x] = find(parent[x]);

Trước khi nén path

Ví dụ gọi find(6), phải đi 6 → 5 → 4 → 3 → 2 → 1.

Sau khi nén path

Sau một lần find(6), các đỉnh trên đường đi có thể trỏ gần như thẳng về root 1.

Không nén path: nhiều lần find có thể lặp lại cùng một đường dài. Có nén path: lần sau tìm lại các đỉnh đó sẽ rất nhanh vì chúng đã trỏ gần root.

6. Vì sao phải swap(a,b)?

Sau a = find(a) và b = find(b), a và b là hai root. Nếu ta luôn làm parent[b] = a mà không xét kích thước, có thể treo cây lớn vào cây nhỏ, làm cây cao lên.

Điểm cần nói rõ: swap(a,b) không phải để sắp xếp số đỉnh. Nó dùng để đảm bảo a là root của cây lớn hơn. Sau đó parent[b] = a nghĩa là cây nhỏ b treo vào cây lớn a.

Không swap: dễ làm cây cao

root 2
root 1345

Nếu treo nhóm lớn vào root nhỏ, đường đi tới root có thể dài hơn.

Có swap: cây nhỏ treo vào cây lớn

root 1
3452

Cây thấp hơn, các thao tác find sau nhanh hơn.

if (sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
Đọc theo tiếng Việt: nếu nhóm của a nhỏ hơn nhóm của b thì đổi chỗ a và b; sau đó luôn treo root b vào root a.

7. Bài tập DSU phân tầng

📘 Cơ bản

  1. Đếm số component của đồ thị vô hướng.
  2. Hỏi hai đỉnh có cùng component không.
  3. Sau mỗi cạnh thêm vào, in số component hiện tại.

📗 Trung bình

  1. Phát hiện cạnh tạo chu trình.
  2. Tìm kích thước component của mỗi đỉnh.
  3. Đếm số cạnh cần thêm để đồ thị liên thông.

📙 Nâng cao

  1. Kruskal tìm cây khung nhỏ nhất.
  2. Offline query connectivity.
  3. DSU rollback định hướng nâng cao.

🐉 HSG

  1. DSU trên cây theo small-to-large.
  2. Kruskal reconstruction tree.
  3. Dynamic connectivity offline.

8. Quiz DSU

Câu 1. Hai đỉnh cùng component khi nào?
Câu 2. Path compression giúp gì?
Câu 3. Vì sao có dòng if (sz[a] < sz[b]) swap(a,b)?
⬅️ Quay lại chương 11