Bài 20.5. Bài tập tổng hợp về DSU và cây khung

Chào mừng các bạn quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật của FullhouseDev! Chúng ta đã cùng nhau khám phá hai công cụ cực kỳ mạnh mẽ trong thế giới đồ thị: DSU (Disjoint Set Union) và Cây Khung Nhỏ Nhất (Minimum Spanning Tree - MST). Hôm nay, chúng ta sẽ không chỉ ôn lại lý thuyết, mà còn đi sâu vào việc áp dụng kết hợp chúng thông qua các bài tập thực tế. Đây là lúc để thấy sức mạnh tổng hợp của DSU và MST khi đối mặt với những bài toán đòi hỏi sự hiểu biết sâu sắc về tính liên thông và tối ưu chi phí trên đồ thị. Hãy cùng bắt đầu hành trình luyện tập đầy thú vị này!

Ôn lại một chút về DSU và MST

Trước khi lao vào giải bài tập, hãy cùng điểm lại những ý chính về hai "nhân vật chính" của chúng ta:

DSU (Disjoint Set Union): Cấu trúc dữ liệu tuyệt vời để quản lý các tập hợp rời rạc. Nó cho phép chúng ta thực hiện hai thao tác chính:
- Find(i): Tìm đại diện (root) của tập hợp chứa phần tử i.
- Union(i, j): Gộp hai tập hợp chứa i và j thành một. Với các kỹ thuật tối ưu như path compression và union by size/rank, DSU đạt hiệu suất gần như hằng số cho mỗi thao tác trong thực tế ($O(\alpha(N))$, với $\alpha$ là hàm Ackermann nghịch đảo). DSU là nền tảng cho các bài toán liên quan đến việc kiểm tra và duy trì tính liên thông của đồ thị.
Cây Khung Nhỏ Nhất (MST): Cho một đồ thị vô hướng có trọng số, MST là cây con bao gồm tất cả các đỉnh của đồ thị gốc sao cho tổng trọng số các cạnh trong cây là nhỏ nhất. MST có ứng dụng rộng rãi, từ thiết kế mạng lưới đến phân tích cluster. Thuật toán Kruskal's là một trong những cách phổ biến để tìm MST, và nó sử dụng DSU một cách rất hiệu quả để kiểm tra xem việc thêm một cạnh có tạo chu trình hay không. Nguyên tắc là chọn các cạnh có trọng số nhỏ nhất mà không làm mất tính "rừng cây" (forest property), tức là không tạo chu trình.

Sự kết hợp giữa DSU và Kruskal's MST là một ví dụ kinh điển về việc sử dụng DSU để giải quyết bài toán đồ thị. Nhưng đó không phải là tất cả! DSU và các biến thể của MST còn xuất hiện trong nhiều bài toán tổng hợp khác. Hãy cùng khám phá qua các ví dụ cụ thể.

Bài toán 1: Kruskal's cổ điển tìm MST

Đây là bài toán cơ bản nhất khi nói đến sự kết hợp của DSU và MST.

Mô tả bài toán

Cho một đồ thị vô hướng liên thông có $N$ đỉnh và $M$ cạnh, mỗi cạnh có một trọng số dương. Hãy tìm tổng trọng số của Cây Khung Nhỏ Nhất của đồ thị này.

Phân tích và Thuật toán

Bài toán này chính là định nghĩa của việc tìm MST trên đồ thị liên thông. Thuật toán Kruskal's là lựa chọn phù hợp và nó tự nhiên yêu cầu DSU.

Chuẩn bị cạnh: Thu thập tất cả các cạnh của đồ thị.
Sắp xếp: Sắp xếp các cạnh theo trọng số tăng dần.
Khởi tạo DSU: Tạo một cấu trúc DSU cho $N$ đỉnh. Ban đầu, mỗi đỉnh là một tập hợp riêng biệt.
Duyệt và Gộp: Lần lượt duyệt qua các cạnh đã sắp xếp, từ cạnh có trọng số nhỏ nhất đến lớn nhất. Với mỗi cạnh $(u, v)$ có trọng số $w$:
- Sử dụng DSU để kiểm tra xem đỉnh $u$ và đỉnh $v$ có thuộc cùng một thành phần liên thông (tập hợp) hay không (Find(u) == Find(v)).
- Nếu chúng chưa liên thông (Find(u) != Find(v)), thêm cạnh này vào cây khung. Cộng trọng số $w$ vào tổng chi phí MST. Sau đó, thực hiện thao tác Union(u, v) để gộp hai thành phần liên thông chứa $u$ và $v$.
- Nếu chúng đã liên thông (Find(u) == Find(v)), việc thêm cạnh này sẽ tạo thành một chu trình, vì vậy chúng ta bỏ qua cạnh này.
Kết thúc: Lặp lại bước 4 cho đến khi thêm được $N-1$ cạnh (đối với đồ thị liên thông), hoặc khi đã duyệt qua hết tất cả $M$ cạnh. Tổng trọng số của các cạnh đã chọn chính là tổng trọng số của MST.

Code C++ minh họa

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// Cấu trúc DSU với tối ưu Path Compression và Union by Size
struct DSU {
    std::vector<int> parent;
    std::vector<int> sz; // Kích thước tập hợp cho union by size

    DSU(int n) {
        parent.resize(n + 1);
        std::iota(parent.begin(), parent.end(), 0); // Khởi tạo parent[i] = i
        sz.assign(n + 1, 1); // Kích thước ban đầu mỗi tập là 1
    }

    // Tìm đại diện (gốc) của tập hợp chứa i với path compression
    int find(int i) {
        if (parent[i] == i)
            return i;
        // Path Compression: gán parent[i] trực tiếp về gốc
        return parent[i] = find(parent[i]);
    }

    // Gộp hai tập hợp chứa i và j với union by size
    // Trả về true nếu gộp thành công, false nếu đã cùng tập hợp
    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            // Union by Size: gộp tập nhỏ hơn vào tập lớn hơn
            if (sz[root_i] < sz[root_j])
                std::swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
            return true; // Hai tập hợp được gộp
        }
        return false; // i và j đã cùng tập hợp
    }
};

// Cấu trúc biểu diễn một cạnh
struct Edge {
    int u, v, w; // u, v là hai đỉnh, w là trọng số

    // Nạp chồng toán tử < để sắp xếp cạnh theo trọng số
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m; // n: số đỉnh, m: số cạnh
    std::cin >> n >> m;

    std::vector<Edge> edges(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    // Bước 1: Sắp xếp các cạnh theo trọng số tăng dần
    std::sort(edges.begin(), edges.end());

    // Bước 2: Khởi tạo DSU
    DSU dsu(n);

    long long mst_cost = 0; // Tổng trọng số MST
    int edges_count = 0; // Số cạnh đã thêm vào MST (cần n-1 cạnh)

    // Bước 3: Duyệt qua các cạnh đã sắp xếp và áp dụng Kruskal's
    for (const auto& edge : edges) {
        // Nếu đỉnh u và v của cạnh hiện tại chưa liên thông
        if (dsu.unite(edge.u, edge.v)) {
            // Thêm cạnh này vào MST
            mst_cost += edge.w;
            edges_count++;

            // Nếu đã thêm đủ n-1 cạnh, ta đã có MST (nếu đồ thị liên thông)
            if (edges_count == n - 1) {
                break; // Dừng sớm
            }
        }
    }

    // Đối với bài toán MST trên đồ thị liên thông, edges_count sẽ luôn đạt n-1.
    // Nếu bài toán cho đồ thị không liên thông và yêu cầu MST, thực chất
    // nó sẽ là Minimum Spanning Forest (MSF). Code trên vẫn tính tổng MSF cost.
    // Để kiểm tra đồ thị liên thông, có thể kiểm tra edges_count == n-1
    // hoặc đếm số components cuối cùng trong DSU.

    if (edges_count == n - 1) {
         std::cout << "Tong trong so Cay Khung Nho Nhat (MST): " << mst_cost << std::endl;
    } else {
        // Nếu đồ thị không liên thông, kết quả là tổng trọng số Rừng Khung Nhỏ Nhất (MSF)
        std::cout << "Do thi khong lien thong, Tong trong so Rung Khung Nho Nhat (MSF): " << mst_cost << std::endl;
    }


    return 0;
}

Giải thích Code

struct DSU: Đây là implementation chuẩn của DSU với parent để lưu cha của mỗi phần tử và sz để hỗ trợ union by size. find sử dụng path compression để làm phẳng cây cấu trúc DSU, còn unite sử dụng union by size để giữ cho cây cân bằng nhất có thể. Hàm unite trả về true nếu thành công gộp hai tập hợp khác nhau, và false nếu hai phần tử đã cùng tập hợp.
struct Edge: Lưu trữ hai đỉnh u, v và trọng số w của cạnh. Chúng ta nạp chồng toán tử < để std::sort có thể sắp xếp vector các cạnh dựa trên trọng số.
main():
- Đọc số đỉnh n và số cạnh m.
- Đọc thông tin m cạnh vào std::vector<Edge> edges.
- Sắp xếp edges theo trọng số tăng dần bằng std::sort.
- Khởi tạo DSU dsu(n). DSU sẽ quản lý các thành phần liên thông trong quá trình thuật toán chạy.
- mst_cost được khởi tạo bằng 0 để tích lũy tổng trọng số MST.
- edges_count đếm số cạnh đã được chọn vào MST.
- Vòng lặp duyệt qua từng cạnh trong danh sách đã sắp xếp.
- Đối với mỗi cạnh edge, chúng ta gọi dsu.unite(edge.u, edge.v).
  - Nếu unite trả về true, điều này có nghĩa là hai đỉnh edge.u và edge.v chưa liên thông trước đó, và cạnh này đã thành công nối hai thành phần khác nhau lại. Đây chính là cạnh ta cần cho MST (vì nó có trọng số nhỏ nhất trong số các cạnh nối hai thành phần này mà chưa được xét). Ta cộng trọng số edge.w vào mst_cost và tăng edges_count.
  - Nếu unite trả về false, hai đỉnh edge.u và edge.v đã liên thông (thông qua các cạnh có trọng số nhỏ hơn đã được xét trước đó). Thêm cạnh này sẽ tạo chu trình, nên ta bỏ qua.
- Khi edges_count đạt n - 1, ta đã chọn đủ số cạnh cho MST của đồ thị liên thông $N$ đỉnh, và có thể dừng thuật toán sớm.
- Cuối cùng, in ra mst_cost. Nếu đồ thị không liên thông, edges_count sẽ nhỏ hơn n-1 và mst_cost sẽ là tổng trọng số của Rừng Khung Nhỏ Nhất (MSF).

Độ phức tạp

Sắp xếp cạnh: $O(M \log M)$.
Các thao tác DSU (Find và Union) với path compression và union by size/rank: Trung bình $O(\alpha(N))$ mỗi thao tác.
Duyệt $M$ cạnh và thực hiện DSU: $O(M \cdot \alpha(N))$.
Tổng độ phức tạp: $O(M \log M + M \cdot \alpha(N))$. Do $M \log M$ thường chiếm ưu thế, độ phức tạp thường được coi là $O(M \log M)$.

Bài toán 2: Kiểm tra tính liên thông động

Bài toán này tập trung vào khả năng của DSU trong việc theo dõi tính liên thông khi các cạnh được thêm vào.

Mô tả bài toán

Cho $N$ đỉnh ban đầu không có cạnh nào. Thực hiện $Q$ thao tác. Mỗi thao tác là một trong hai loại:

Thêm một cạnh vô hướng giữa đỉnh $u$ và đỉnh $v$.
Kiểm tra xem đỉnh $u$ và đỉnh $v$ có liên thông với nhau (thuộc cùng một thành phần liên thông) hay không.

Phân tích và Thuật toán

Bài toán này là một ứng dụng trực tiếp và hoàn hảo của DSU. Khi có thao tác thêm cạnh $(u, v)$, chúng ta chỉ đơn giản là gộp hai tập hợp chứa $u$ và $v$ bằng thao tác Union. Khi có thao tác kiểm tra tính liên thông giữa $u$ và $v$, chúng ta chỉ cần xem chúng có cùng "đại diện" (root) trong cấu trúc DSU hay không bằng thao tác Find.

Khởi tạo DSU: Tạo một cấu trúc DSU cho $N$ đỉnh.
Xử lý thao tác: Duyệt qua $Q$ thao tác.
- Nếu là thao tác thêm cạnh $(u, v)$: Gọi unite(u, v).
- Nếu là thao tác kiểm tra $(u, v)$: So sánh find(u) và find(v). Nếu bằng nhau, chúng liên thông. Ngược lại, không liên thông.

Code C++ minh họa

#include <iostream>
#include <vector>
#include <numeric>

// Cấu trúc DSU (tương tự như trên)
struct DSU {
    std::vector<int> parent;
    std::vector<int> sz;

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

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

    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (sz[root_i] < sz[root_j])
                std::swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
            return true;
        }
        return false;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, q; // n: số đỉnh, q: số thao tác
    std::cin >> n >> q;

    DSU dsu(n); // Khởi tạo DSU với n đỉnh

    // Xử lý Q thao tác
    for (int k = 0; k < q; ++k) {
        int type; // Loại thao tác: 1 - thêm cạnh, 2 - kiểm tra liên thông
        std::cin >> type;
        if (type == 1) {
            int u, v;
            std::cin >> u >> v;
            // Thêm cạnh (u, v) tương đương với gộp tập hợp chứa u và v
            dsu.unite(u, v);
        } else if (type == 2) {
            int u, v;
            std::cin >> u >> v;
            // Kiểm tra liên thông giữa u và v <=> kiểm tra chúng có cùng gốc không
            if (dsu.find(u) == dsu.find(v)) {
                std::cout << "YES\n"; // Liên thông
            } else {
                std::cout << "NO\n"; // Không liên thông
            }
        }
    }

    return 0;
}

Giải thích Code

Cấu trúc DSU hoàn toàn giống như trong Bài toán 1, cung cấp các thao tác find và unite hiệu quả.
main():
- Đọc số đỉnh n và số thao tác q.
- Khởi tạo DSU dsu(n). Ban đầu mỗi đỉnh là một tập hợp riêng.
- Vòng lặp $Q$ lần để đọc và xử lý từng thao tác.
- Nếu type == 1 (thêm cạnh): Đọc hai đỉnh u, v và gọi dsu.unite(u, v). DSU tự động cập nhật cấu trúc để phản ánh rằng u và v cùng thành phần liên thông.
- Nếu type == 2 (kiểm tra liên thông): Đọc hai đỉnh u, v và so sánh kết quả của dsu.find(u) và dsu.find(v). Nếu hai giá trị root bằng nhau, u và v thuộc cùng một tập hợp (thành phần liên thông) và ta in "YES". Ngược lại, in "NO".

Độ phức tạp

Khởi tạo DSU: $O(N)$.
Mỗi thao tác DSU (Find, Union): Trung bình $O(\alpha(N))$.
Tổng $Q$ thao tác: $O(Q \cdot \alpha(N))$.
Tổng độ phức tạp: $O(N + Q \cdot \alpha(N))$.

Bài toán 3: Kết nối các thành phần với chi phí tối thiểu

Đây là một biến thể nâng cao hơn, nơi DSU giúp chúng ta "tiền xử lý" đồ thị và MST được áp dụng trên các thành phần liên thông.

Mô tả bài toán

Cho $N$ thành phố. Ban đầu có $M$ con đường miễn phí (chi phí 0) đã tồn tại. Ngoài ra, có $K$ dự án xây dựng đường mới tiềm năng, mỗi dự án nối hai thành phố với một chi phí nhất định ($> 0$). Tìm tổng chi phí nhỏ nhất để tất cả $N$ thành phố trở nên liên thông với nhau.

Phân tích và Thuật toán

Điểm mấu chốt là các con đường miễn phí ban đầu đã tạo ra một số thành phần liên thông sẵn có. Chúng ta có thể coi mỗi thành phần này như một "siêu đỉnh". Bài toán trở thành: tìm cách nối các siêu đỉnh này lại với nhau bằng các cạnh có chi phí dương sao cho tổng chi phí là nhỏ nhất. Đây chính là bài toán tìm MST trên đồ thị mới mà các đỉnh là các thành phần liên thông ban đầu.

Tiền xử lý miễn phí: Sử dụng DSU để xử lý $M$ con đường miễn phí. Đối với mỗi đường $(u, v)$ chi phí 0, gọi unite(u, v). Sau bước này, cấu trúc DSU phản ánh các thành phần liên thông được tạo bởi các con đường miễn phí. Ta có thể theo dõi số lượng thành phần liên thông hiện tại.
Chuẩn bị cạnh có chi phí: Thu thập $K$ dự án đường mới (các cạnh có chi phí dương).
Sắp xếp: Sắp xếp $K$ dự án này theo chi phí tăng dần.
Áp dụng Kruskal's trên các thành phần: Duyệt qua các dự án đã sắp xếp. Với mỗi dự án nối hai thành phố $u, v$ với chi phí $w$:
- Sử dụng DSU (đã được cập nhật bởi các đường miễn phí) để kiểm tra xem $u$ và $v$ có thuộc cùng một thành phần liên thông hiện tại hay không (Find(u) == Find(v)).
- Nếu chúng chưa liên thông (Find(u) != Find(v)), nghĩa là dự án này nối hai thành phần liên thông khác nhau. Đây là một cạnh tiềm năng cho MST của các siêu đỉnh. Ta chọn dự án này, cộng chi phí $w$ vào tổng chi phí, và thực hiện unite(u, v) để gộp hai thành phần này lại. Đồng thời, giảm số lượng thành phần liên thông đi 1.
- Nếu chúng đã liên thông (Find(u) == Find(v)), bỏ qua dự án này vì nó chỉ nối hai thành phố vốn đã liên thông, không giúp kết nối các thành phần lớn hơn.
Kết thúc: Lặp lại bước 4 cho đến khi chỉ còn 1 thành phần liên thông duy nhất (tất cả các thành phố đã liên thông), hoặc khi đã duyệt hết $K$ dự án. Tổng chi phí tích lũy chính là chi phí nhỏ nhất.

Code C++ minh họa

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// Cấu trúc DSU (có thêm biến đếm số thành phần)
struct DSU {
    std::vector<int> parent;
    std::vector<int> sz;
    int num_components; // Số thành phần liên thông hiện tại

    DSU(int n) {
        parent.resize(n + 1);
        std::iota(parent.begin(), parent.end(), 0);
        sz.assign(n + 1, 1);
        num_components = n; // Ban đầu có n thành phần, mỗi đỉnh một
    }

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

    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (sz[root_i] < sz[root_j])
                std::swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
            num_components--; // Giảm số thành phần khi gộp thành công
            return true;
        }
        return false;
    }
};

// Cấu trúc Edge cho các dự án đường mới
struct Edge {
    int u, v, w; // u, v: thành phố, w: chi phí

    bool operator<(const Edge& other) const {
        return w < other.w; // Sắp xếp theo chi phí tăng dần
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, k; // n: số thành phố, m: đường miễn phí, k: dự án đường mới
    std::cin >> n >> m >> k;

    DSU dsu(n);

    // Bước 1: Xử lý các con đường miễn phí (chi phí 0)
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        dsu.unite(u, v); // Gộp các thành phố đã nối miễn phí
    }

    // Bước 2: Đọc và lưu trữ các dự án đường mới (chi phí > 0)
    std::vector<Edge> potential_roads(k);
    for (int i = 0; i < k; ++i) {
        std::cin >> potential_roads[i].u >> potential_roads[i].v >> potential_roads[i].w;
    }

    // Sắp xếp các dự án theo chi phí tăng dần
    std::sort(potential_roads.begin(), potential_roads.end());

    long long total_cost = 0; // Tổng chi phí để kết nối
    int edges_added = 0; // Số cạnh chi phí dương đã thêm

    // Bước 3: Áp dụng Kruskal's trên các dự án để nối các thành phần liên thông
    for (const auto& road : potential_roads) {
        // Nếu 2 thành phố thuộc 2 thành phần khác nhau trong cấu trúc DSU hiện tại
        if (dsu.unite(road.u, road.v)) {
            // Chọn dự án này để nối 2 thành phần
            total_cost += road.w;
            edges_added++;
            // Nếu chỉ còn 1 thành phần, tất cả đã liên thông
            if (dsu.num_components == 1) {
                break; // Đã hoàn thành mục tiêu
            }
        }
    }

    // Kiểm tra xem cuối cùng tất cả N thành phố có liên thông không
    // Nếu dsu.num_components > 1 sau khi duyệt hết K dự án,
    // nghĩa là không thể kết nối tất cả các thành phố với các dự án có sẵn.
    // Tùy yêu cầu bài toán, có thể in -1 hoặc thông báo lỗi.
    // Ở đây, giả định bài toán luôn có cách kết nối.
    if (dsu.num_components == 1) {
        std::cout << "Chi phi ket noi toi thieu: " << total_cost << std::endl;
    } else {
        // Nếu không thể kết nối tất cả (vẫn còn >1 thành phần)
        // In ra thông báo hoặc giá trị đặc biệt (-1 thường dùng)
        // std::cout << -1 << std::endl; // Hoặc in ra total_cost nếu yêu cầu kết nối MSF
        std::cout << "Khong the ket noi tat ca thanh pho. Chi phi ket noi duoc (toi da): " << total_cost << std::endl;
    }


    return 0;
}

Giải thích Code

struct DSU: Tương tự các bài trước, nhưng có thêm num_components được khởi tạo bằng n. Mỗi lần unite thành công (gộp hai tập khác nhau), num_components giảm đi 1.
struct Edge: Lưu trữ thông tin các dự án đường mới (chi phí dương). Nạp chồng < để sắp xếp theo chi phí.
main():
- Đọc $N, M, K$.
- Khởi tạo DSU dsu(n). dsu.num_components ban đầu là $N$.
- Vòng lặp đầu tiên xử lý $M$ con đường miễn phí. Đối với mỗi cặp $(u, v)$, gọi dsu.unite(u, v). Chi phí 0 nên không cộng vào total_cost, nhưng DSU được cập nhật và num_components giảm đi nếu các thành phố được gộp.
- Đọc $K$ dự án đường mới vào potential_roads.
- Sắp xếp potential_roads theo chi phí tăng dần.
- Vòng lặp thứ hai duyệt qua các potential_roads.
- Đối với mỗi dự án nối $(u, v)$ với chi phí $w$, gọi dsu.unite(u, v).
  - Nếu unite trả về true, nghĩa là dự án này nối hai thành phần liên thông khác nhau (tính đến thời điểm hiện tại, sau khi đã xử lý các đường miễn phí và các dự án chi phí nhỏ hơn). Ta chấp nhận dự án này, cộng chi phí w vào total_cost, và dsu.num_components giảm đi 1.
  - Nếu unite trả về false, dự án nối hai thành phố đã liên thông, bỏ qua.
- Kiểm tra dsu.num_components == 1. Nếu đúng, tất cả các thành phố đã được nối thành một thành phần duy nhất, tức là đã liên thông. Ta đã tìm được chi phí nhỏ nhất và có thể dừng vòng lặp.
- Sau vòng lặp, kiểm tra lại dsu.num_components. Nếu nó bằng 1, ta đã thành công và in total_cost. Nếu lớn hơn 1, nghĩa là không thể kết nối tất cả các thành phố với các dự án có sẵn (thành đồ thị liên thông đầy đủ). Tùy bài toán cụ thể mà xử lý (ví dụ: in -1 hoặc in total_cost nếu nó là MSF của các thành phần).

Độ phức tạp

Khởi tạo DSU: $O(N)$.
Xử lý $M$ đường miễn phí: $O(M \cdot \alpha(N))$.
Sắp xếp $K$ dự án: $O(K \log K)$.
Duyệt $K$ dự án và thực hiện DSU: $O(K \cdot \alpha(N))$.
Tổng độ phức tạp: $O(N + M \cdot \alpha(N) + K \log K + K \cdot \alpha(N))$. Chủ yếu là $O(M \cdot \alpha(N) + K \log K)$.

Bài toán 4: Đếm số thành phần liên thông

Bài toán này là một ứng dụng đơn giản nhưng hữu ích của DSU để phân tích cấu trúc của đồ thị.

Mô tả bài toán

Cho một đồ thị vô hướng có $N$ đỉnh và $M$ cạnh. Tìm số lượng các thành phần liên thông (connected components) trong đồ thị này.

Phân tích và Thuật toán

DSU theo dõi số lượng các tập hợp rời rạc một cách tự nhiên. Mỗi tập hợp trong DSU sau khi xử lý tất cả các cạnh sẽ tương ứng với một thành phần liên thông của đồ thị.

Khởi tạo DSU: Tạo một cấu trúc DSU cho $N$ đỉnh. Ban đầu, có $N$ thành phần liên thông riêng biệt.
Xử lý cạnh: Duyệt qua tất cả $M$ cạnh của đồ thị. Đối với mỗi cạnh $(u, v)$, thực hiện unite(u, v). Mỗi lần unite thành công (gộp hai thành phần khác nhau), số lượng thành phần liên thông giảm đi 1.
Kết quả: Sau khi xử lý hết tất cả $M$ cạnh, giá trị của num_components trong cấu trúc DSU chính là số lượng thành phần liên thông của đồ thị. (Hoặc bạn có thể đếm số đỉnh $i$ mà parent[i] == i sau khi xử lý tất cả các cạnh).

Code C++ minh họa

#include <iostream>
#include <vector>
#include <numeric>

// Cấu trúc DSU (có biến đếm số thành phần)
struct DSU {
    std::vector<int> parent;
    std::vector<int> sz;
    int num_components; // Số thành phần liên thông hiện tại

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

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

    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (sz[root_i] < sz[root_j])
                std::swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
            num_components--; // Giảm số thành phần khi gộp
            return true;
        }
        return false;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m; // n: số đỉnh, m: số cạnh
    std::cin >> n >> m;

    DSU dsu(n); // Khởi tạo DSU với n đỉnh

    // Duyệt qua tất cả các cạnh và gộp các tập hợp
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        dsu.unite(u, v);
    }

    // Số thành phần liên thông chính là dsu.num_components
    std::cout << "So thanh phan lien thong: " << dsu.num_components << std::endl;

    return 0;
}

Giải thích Code

Cấu trúc DSU hoàn toàn giống phiên bản trong Bài toán 3, bao gồm cả việc theo dõi biến num_components.
main():
- Đọc số đỉnh n và số cạnh m.
- Khởi tạo DSU dsu(n). Ban đầu có n thành phần liên thông.
- Vòng lặp duyệt qua $M$ cạnh. Đối với mỗi cạnh $(u, v)$, gọi dsu.unite(u, v). Mỗi lần unite thành công (gộp hai thành phần khác nhau), dsu.num_components tự động giảm đi 1.
- Sau khi xử lý hết $M$ cạnh, dsu.num_components chứa giá trị cuối cùng của số lượng thành phần liên thông trong đồ thị. In giá trị này ra.

Độ phức tạp

Khởi tạo DSU: $O(N)$.
Xử lý $M$ cạnh: $O(M \cdot \alpha(N))$.
Tổng độ phức tạp: $O(N + M \cdot \alpha(N))$.

Bài tập ví dụ:

Thí nghiệm ở Berland

Trong một buổi nghiên cứu về nguyên lý tiếp thị, FullHouse Dev được giao một bài toán thú vị về phản ứng hóa học. Họ cần phân tích cách các giọt hóa chất tương tác trên một bề mặt phòng thí nghiệm, điều này tương tự như cách các chiến dịch tiếp thị lan truyền và kết nối với nhau. Với tinh thần nhiệt huyết, FullHouse Dev bắt đầu nghiên cứu vấn đề này.

Bài toán

FullHouse Dev có một sàn phòng thí nghiệm kích thước $n × m$. Khi một giọt hóa chất rơi xuống một ô, nó sẽ kết hợp với các giọt khác ở các ô liền kề (chung cạnh) để tạo thành một giọt lớn hơn. Lưu ý: Nếu một giọt hóa chất rơi vào cùng một ô, kích thước không thay đổi và tất cả các chỉ số đều bắt đầu từ 1.

INPUT FORMAT:

Dòng đầu tiên chứa ba số nguyên $n$, $m$ và $q$ - số hàng, số cột và số truy vấn.
$q$ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại:
- Loại 1: Gồm ba số nguyên 1, $x$ và $y$ - tọa độ của ô mà giọt hóa chất rơi xuống
- Loại 0: In ra số lượng giọt lớn đã được tạo thành cho đến thời điểm hiện tại

OUTPUT FORMAT:

Với mỗi truy vấn loại 0, in ra tổng số giọt lớn đã được tạo thành.

Ràng buộc:

$1 \leq n, m \leq 1000$
$1 \leq q \leq 100000$
$1 \leq x \leq n$
$1 \leq y \leq m$

Ví dụ

INPUT

OUTPUT

1
1

Giải thích

Ban đầu, một giọt rơi vào ô (2,1), sau đó một giọt khác rơi vào ô (2,2). Do hai ô này liền kề nhau nên chúng kết hợp thành một thành phần liên thông. Khi truy vấn loại 0 đầu tiên được thực hiện, có 1 thành phần liên thông. Tiếp theo, một giọt rơi vào ô (3,2), nó kết hợp với giọt ở ô (2,2) tạo thành một thành phần liên thông. Khi truy vấn loại 0 thứ hai được thực hiện, vẫn chỉ có 1 thành phần liên thông. Tuyệt vời! Bài toán này là một ứng dụng kinh điển của cấu trúc dữ liệu Hợp nhất tập không giao nhau (Disjoint Set Union - DSU) trên lưới (grid).

Hướng giải ngắn gọn như sau:

Biểu diễn: Biến đổi lưới 2D kích thước n x m thành một mảng 1D có kích thước n * m. Mỗi ô (x, y) trên lưới (sử dụng chỉ mục 1-based như đề bài) có thể được ánh xạ tới một chỉ mục idx trong mảng 1D, ví dụ idx = (x - 1) * m + (y - 1).
Cấu trúc DSU: Sử dụng cấu trúc DSU để quản lý các thành phần liên thông của các ô đã có giọt hóa chất.
- Cần một mảng parent kích thước n*m để lưu trữ cha của mỗi phần tử.
- (Tùy chọn nhưng nên có) Cần mảng size (hoặc rank) để tối ưu hóa phép union (hợp nhất theo kích thước/hạng).
- Cần một mảng boolean isActive kích thước n x m (hoặc n*m trong 1D) để đánh dấu xem ô (x, y) đã có giọt hóa chất hay chưa.
- Cần một biến đếm num_components để lưu số lượng thành phần liên thông hiện tại (tổng số giọt lớn).
Khởi tạo:
- Ban đầu, tất cả các ô đều không có giọt (isActive = false).
- Biến num_components khởi tạo bằng 0.
- Cấu trúc DSU được khởi tạo sao cho mỗi phần tử là cha của chính nó.
Xử lý truy vấn Loại 1 (đặt giọt tại (x, y)):
- Chuyển tọa độ (x, y) sang chỉ mục 1D idx.
- Kiểm tra nếu ô (x, y) đã isActive: Nếu có, không làm gì cả và kết thúc xử lý truy vấn này (kích thước giọt không đổi).
- Nếu ô (x, y) chưa isActive:
  - Đánh dấu ô (x, y) là isActive.
  - Tăng num_components lên 1. (Một ô mới được kích hoạt ban đầu được xem là một thành phần mới).
  - Tìm chỉ mục 1D idx của ô (x, y).
  - Thực hiện phép union giữa idx và các ô lân cận (nx, ny) (chung cạnh) mà đang isActive. Các ô lân cận là (x-1, y), (x+1, y), (x, y-1), (x, y+1).
  - Đối với mỗi ô lân cận (nx, ny) hợp lệ (trong phạm vi lưới) và đang isActive:
    - Tìm chỉ mục 1D n_idx của (nx, ny).
    - Thực hiện phép union(idx, n_idx).
    - Quan trọng: Nếu phép union này thực sự hợp nhất hai tập hợp khác nhau (tức là find(idx) khác find(n_idx) trước khi hợp nhất), điều đó có nghĩa là hai thành phần liên thông đã nhập lại thành một. Do đó, bạn cần giảm num_components đi 1.
Xử lý truy vấn Loại 0 (in số giọt lớn):
- In giá trị hiện tại của num_components.
Tối ưu DSU: Để đảm bảo hiệu quả cho q truy vấn, cần triển khai các tối ưu cơ bản của DSU:
- Nén đường đi (Path Compression) trong hàm find.
- Hợp nhất theo kích thước hoặc hạng (Union by Size/Rank) trong hàm union.

Cách tiếp cận này cho phép theo dõi số lượng thành phần liên thông (số giọt lớn) một cách hiệu quả khi các ô mới được kích hoạt và hợp nhất với các thành phần hiện có. Độ phức tạp cho mỗi thao tác DSU gần như là hằng số (chính xác là O(alpha(N)), với alpha là nghịch đảo hàm Ackermann, rất nhỏ).

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.