Khóa học CTDL và GT

Bài 20.1. Cấu trúc dữ liệu Disjoint Set Union (DSU)

Chào mừng các bạn quay trở lại với chuỗi bài về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau "mổ xẻ" một cấu trúc dữ liệu cực kỳ mạnh mẽ và vô cùng hiệu quả trong việc giải quyết các bài toán liên quan đến quản lý các tập hợp rời rạc (không giao nhau) và thực hiện các thao tác hợp nhất chúng. Đó chính là Disjoint Set Union (DSU), hay còn được biết đến với cái tên Union-Find.

Nghe tên có vẻ hàn lâm, nhưng ý tưởng cốt lõi của DSU lại đơn giản đến bất ngờ. Hãy cùng đi sâu vào nó nhé!

DSU là gì? Khi nào thì dùng DSU?

Hãy tưởng tượng bạn có một tập hợp các phần tử độc lập. Ban đầu, mỗi phần tử này là một "tập hợp" riêng của chính nó. Theo thời gian, bạn có thể nhận được yêu cầu hợp nhất hai tập hợp lại với nhau (vì các phần tử trong đó có một mối liên hệ nào đó). Đồng thời, bạn cần có khả năng kiểm tra nhanh chóng xem hai phần tử bất kỳ có đang nằm trong cùng một tập hợp hay không.

Đây chính xác là vấn đề mà DSU được sinh ra để giải quyết!

Cốt lõi của DSU là khả năng thực hiện hai thao tác chính (tên gọi có thể khác nhau tùy nguồn):

1. Find (hoặc findSet, getParent): Cho một phần tử x, trả về phần tử đại diện (representative) của tập hợp chứa x. Tất cả các phần tử trong cùng một tập hợp sẽ có cùng một phần tử đại diện.
2. Union (hoặc unionSets, merge, unite): Hợp nhất hai tập hợp chứa hai phần tử x và y thành một tập hợp duy nhất. Sau thao tác này, x và y (và tất cả các phần tử ban đầu thuộc tập hợp của chúng) sẽ nằm trong cùng một tập hợp mới.

Các bài toán điển hình sử dụng DSU bao gồm:

• Tìm kiếm các thành phần liên thông (connected components) trong một đồ thị vô hướng.
• Kiểm tra xem việc thêm một cạnh mới vào đồ thị vô hướng có tạo ra chu trình (cycle) hay không.
• Giải thuật Kruskal tìm cây bao trùm nhỏ nhất (Minimum Spanning Tree - MST).
• Các bài toán quản lý mạng, kết nối các đối tượng, v.v.

DSU nổi bật nhờ tốc độ thực thi cực kỳ nhanh cho các thao tác Find và Union trên thực tế, gần như là thời gian hằng số trung bình (amortized constant time) khi có các tối ưu hợp lý.

Biểu diễn tập hợp trong DSU

Làm thế nào để biểu diễn các tập hợp rời rạc này và mối quan hệ "cùng tập hợp" một cách hiệu quả? Ý tưởng phổ biến nhất là sử dụng một cấu trúc cây (tree).

• Mỗi tập hợp được biểu diễn bởi một cây, trong đó gốc (root) của cây chính là phần tử đại diện của tập hợp đó.
• Mỗi nút trong cây (trừ gốc) có một nút cha (parent).
• Ban đầu, với N phần tử, chúng ta sẽ có N cây, mỗi cây chỉ có một nút duy nhất chính là phần tử đó, và nó cũng là gốc của chính nó (cha của nó là chính nó).

Chúng ta có thể lưu trữ cấu trúc này bằng một mảng (hoặc vector) parent, trong đó parent[i] lưu chỉ số của phần tử cha của phần tử i. Nếu parent[i] == i, thì i là gốc của tập hợp chứa nó.

Ví dụ: parent = [0, 0, 1, 3, 3]

• Phần tử 0 là gốc (parent[0] == 0). Tập hợp {0, 1, 2}.
• Phần tử 1 có cha là 0.
• Phần tử 2 có cha là 1.
• Phần tử 3 là gốc (parent[3] == 3). Tập hợp {3, 4}.
• Phần tử 4 có cha là 3.

Như vậy, chúng ta có hai tập hợp: {0, 1, 2} và {3, 4}.

Triển khai cơ bản (và vấn đề của nó)

Hãy xem xét việc triển khai Find và Union dựa trên ý tưởng cơ bản này.

• Find(i): Để tìm phần tử đại diện của i, ta đi ngược lên cây từ i theo liên kết cha cho đến khi gặp nút mà cha của nó là chính nó (nút gốc).
• Union(i, j): Để hợp nhất tập hợp chứa i và tập hợp chứa j, ta tìm phần tử đại diện của i (gọi là root_i) và phần tử đại diện của j (gọi là root_j). Nếu root_i và root_j khác nhau, nghĩa là i và j đang ở trong hai tập hợp khác nhau. Ta chỉ việc "treo" gốc của một cây (ví dụ root_j) vào gốc của cây kia (root_i) bằng cách đặt parent[root_j] = root_i. Nếu root_i == root_j, tức là i và j đã cùng tập hợp rồi, không cần làm gì cả.

#include <vector>
#include <numeric> // std::iota

// Triển khai DSU cơ bản (Chưa tối ưu)
class BasicDSU {
private:
    std::vector<int> parent;

public:
    // Khởi tạo N tập hợp, mỗi tập hợp chứa một phần tử từ 0 đến N-1
    BasicDSU(int n) {
        parent.resize(n);
        // Ban đầu, mỗi phần tử là cha của chính nó (là gốc)
        std::iota(parent.begin(), parent.end(), 0); // parent[i] = i for i from 0 to n-1
    }

    // Tìm phần tử đại diện của tập hợp chứa i
    int find_basic(int i) {
        // Đi ngược lên cây cho đến khi gặp gốc (parent[i] == i)
        while (parent[i] != i) {
            i = parent[i];
        }
        return i;
    }

    // Hợp nhất tập hợp chứa i và tập hợp chứa j
    void union_basic(int i, int j) {
        int root_i = find_basic(i);
        int root_j = find_basic(j);

        // Nếu hai phần tử đại diện khác nhau, tức là chúng ở hai tập hợp khác nhau
        if (root_i != root_j) {
            // Gắn gốc của tập hợp j vào gốc của tập hợp i
            parent[root_j] = root_i;
        }
    }

    // Kiểm tra xem hai phần tử có cùng tập hợp hay không
    bool are_connected_basic(int i, int j) {
        return find_basic(i) == find_basic(j);
    }
};

Vấn đề: Triển khai cơ bản này có thể hoạt động, nhưng nó không hiệu quả. Hãy nghĩ đến trường hợp chúng ta luôn Union một tập hợp mới vào cùng một gốc. Điều này có thể tạo ra một cây rất "cao" hoặc "sâu" (một danh sách liên kết). Khi đó, thao tác find_basic cho một phần tử ở cuối danh sách này sẽ phải đi qua tất cả các nút từ lá lên đến gốc, mất thời gian O(N) trong trường hợp xấu nhất, với N là tổng số phần tử. Với nhiều thao tác, điều này có thể khiến hiệu suất giảm đáng kể.

Để DSU thực sự mạnh mẽ, chúng ta cần các kỹ thuật tối ưu!

Tối ưu hóa hiệu suất của DSU

Có hai kỹ thuật tối ưu hóa chính thường được kết hợp với nhau để làm phẳng cấu trúc cây và giảm thời gian cho các thao tác Find và Union:

1. Nén đường đi (Path Compression): Kỹ thuật này được áp dụng trong thao tác Find. Khi tìm gốc của một phần tử i, trên đường đi từ i lên đến gốc, ta sẽ trỏ trực tiếp tất cả các nút trên đường đi đó (trừ gốc) về thẳng nút gốc. Lần sau khi gọi Find cho bất kỳ nút nào trên đường đi này, nó sẽ tìm thấy gốc ngay lập tức hoặc chỉ sau một vài bước.

   // Find operation with Path Compression
   int find(int i) {
       // Base case: if i is the root
       if (parent[i] == i) {
           return i;
       }
       // Recursive call to find the root
       // On the way back, set parent[i] directly to the root
       return parent[i] = find(parent[i]);
   }
   

   Giải thích: Khi đệ quy trả về gốc (find(parent[i])), giá trị gốc đó được gán lại cho parent[i]. Điều này làm phẳng cây hiệu quả.

2. Hợp nhất theo kích thước (Union by Size) hoặc Hợp nhất theo hạng (Union by Rank): Kỹ thuật này được áp dụng trong thao tác Union để giữ cho cây càng "lùn" càng tốt.

   • Union by Size: Duy trì một mảng sz (hoặc size) lưu trữ kích thước của tập hợp (số lượng phần tử) tại nút gốc của tập hợp đó. Khi hợp nhất hai tập hợp, ta luôn gắn gốc của cây có kích thước nhỏ hơn vào gốc của cây có kích thước lớn hơn. Điều này đảm bảo chiều cao của cây không tăng lên quá nhanh.
   • Union by Rank: Duy trì một mảng rank (hoặc height) lưu trữ "hạng" của cây (xấp xỉ chiều cao logarit của cây). Khi hợp nhất, ta gắn gốc của cây có hạng thấp hơn vào gốc của cây có hạng cao hơn. Nếu hai gốc có cùng hạng, ta gắn tùy ý và tăng hạng của gốc mới lên 1.

Kết hợp cả hai kỹ thuật tối ưu này (thường là nén đường đi và hợp nhất theo kích thước/hạng), thời gian thực thi trung bình (amortized time complexity) cho mỗi thao tác Find và Union là O(α(N)), trong đó α(N) là hàm Ackermann ngược, một hàm tăng trưởng cực kỳ chậm. Đối với mọi kích thước tập dữ liệu thực tế mà chúng ta có thể gặp, α(N) nhỏ hơn 5. Vì vậy, về mặt lý thuyết và thực tế, DSU tối ưu hoạt động gần như trong thời gian hằng số O(1) cho mỗi thao tác!

Triển khai DSU tối ưu bằng C++

Chúng ta sẽ triển khai DSU kết hợp nén đường đi và hợp nhất theo kích thước.

#include <vector>
#include <numeric> // std::iota
#include <iostream> // For examples

class DSU {
private:
    std::vector<int> parent;
    std::vector<int> sz; // sz[i] stores the size of the set if i is the root

public:
    // Constructor: Initialize N disjoint sets, each with one element
    DSU(int n) {
        parent.resize(n);
        std::iota(parent.begin(), parent.end(), 0); // parent[i] = i for i = 0..n-1
        sz.assign(n, 1); // Initially, each set has size 1
    }

    // Find operation with Path Compression
    // Returns the representative (root) of the set containing element i
    int find(int i) {
        // Base case: if i is the root (parent[i] == i)
        if (parent[i] == i) {
            return i;
        }
        // Recursive call to find the root
        // Path compression: set parent[i] directly to the root found
        return parent[i] = find(parent[i]);
    }

    // Union operation by Size
    // Merges the sets containing elements i and j
    void unite(int i, int j) {
        int root_i = find(i); // Find the representative of i's set
        int root_j = find(j); // Find the representative of j's set

        // If they are already in the same set, do nothing
        if (root_i != root_j) {
            // Union by size: Attach the root of the smaller tree to the root of the larger tree
            if (sz[root_i] < sz[root_j]) {
                std::swap(root_i, root_j); // Ensure root_i points to the root of the larger tree
            }
            // Attach root_j to root_i
            parent[root_j] = root_i;
            // Update the size of the combined set
            sz[root_i] += sz[root_j];
        }
    }

    // Helper function to check if two elements are in the same set
    bool are_connected(int i, int j) {
        return find(i) == find(j);
    }

    // Optional: Get the size of the set containing element i
    int get_set_size(int i) {
        return sz[find(i)];
    }

    // Optional: Count the number of disjoint sets
    int count_sets() {
        int count = 0;
        for (int i = 0; i < parent.size(); ++i) {
            if (parent[i] == i) { // If i is a root
                count++;
            }
        }
        return count;
    }

    // Optional: Access parent array (for debugging/specific needs, typically not public)
    // std::vector<int>& get_parent_array() { return parent; }
};

Giải thích Code:

• DSU(int n) Constructor:

  • Khởi tạo vector parent có kích thước n.
  • std::iota(parent.begin(), parent.end(), 0): Hàm này từ <numeric> giúp gán giá trị từ 0 đến n-1 cho các phần tử của parent. Nghĩa là parent[i] = i ban đầu, mỗi phần tử là gốc của tập hợp riêng.
  • Khởi tạo vector sz (size) có kích thước n, tất cả các giá trị ban đầu là 1, vì mỗi tập hợp ban đầu chỉ có 1 phần tử.

• find(int i):

  • Đây là hàm Find tối ưu với nén đường đi.
  • Dòng if (parent[i] == i): Điều kiện dừng đệ quy, nếu i là gốc, trả về i.
  • Dòng return parent[i] = find(parent[i]);: Đây là phần quan trọng nhất của nén đường đi. Nó đệ quy gọi find cho parent[i] để tìm ra gốc cuối cùng. Khi kết quả được trả về, nó gán gốc đó trực tiếp vào parent[i] trước khi trả về kết quả. Điều này "ép" i và tất cả các nút trên đường đi từ i lên gốc (trong các lần gọi đệ quy tiếp theo cho cùng một đường đi) trỏ thẳng về gốc, làm phẳng cây.

• unite(int i, int j):

  • Đây là hàm Union tối ưu theo kích thước.
  • Tìm gốc của i và j bằng cách gọi find(i) và find(j).
  • Nếu root_i != root_j: Nghĩa là i và j đang ở trong hai tập hợp khác nhau, cần hợp nhất.
  • if (sz[root_i] < sz[root_j]) std::swap(root_i, root_j);: So sánh kích thước của hai tập hợp (lưu tại gốc của chúng). Đảm bảo rằng root_i luôn trỏ đến gốc của tập hợp lớn hơn (hoặc bằng).
  • parent[root_j] = root_i;: Gắn gốc của tập hợp nhỏ hơn (root_j) vào gốc của tập hợp lớn hơn (root_i).
  • sz[root_i] += sz[root_j];: Cập nhật kích thước của tập hợp mới (chỉ cần tăng kích thước của gốc mới).

• are_connected(int i, int j):

  • Kiểm tra xem i và j có cùng gốc hay không. Đơn giản chỉ cần so sánh kết quả của find(i) và find(j).

• get_set_size(int i): Trả về kích thước của tập hợp chứa i. Để làm được điều này, trước hết phải tìm gốc của i, sau đó truy cập sz tại chỉ số của gốc đó.

• count_sets(): Đếm số lượng tập hợp rời rạc hiện tại. Đơn giản là đếm số lượng phần tử mà parent[i] == i (số lượng gốc).

Ví dụ minh họa 1: Tìm thành phần liên thông trong đồ thị

DSU là công cụ lý tưởng để tìm và quản lý các thành phần liên thông trong một đồ thị vô hướng. Ban đầu, mỗi đỉnh là một thành phần riêng. Khi ta duyệt qua các cạnh (u, v), nếu u và v chưa liên thông (khác tập hợp trong DSU), ta hợp nhất tập hợp của chúng. Số lượng tập hợp còn lại chính là số thành phần liên thông.

#include <iostream>
#include <vector>
#include <numeric>
#include <utility> // For std::pair

// Include the DSU class definition here
// class DSU { ... };

int main() {
    // Giả sử đồ thị có 6 đỉnh (0 đến 5)
    int num_vertices = 6;
    DSU dsu(num_vertices);

    // Các cạnh của đồ thị
    std::vector<std::pair<int, int>> edges = {
        {0, 1}, // Kết nối 0 và 1
        {1, 2}, // Kết nối 1 và 2
        {3, 4}  // Kết nối 3 và 4
        // Đỉnh 5 là đỉnh cô lập
    };

    std::cout << "--- Ví dụ 1: Tìm thành phần liên thông ---" << std::endl;
    std::cout << "Processing edges:" << std::endl;

    // Duyệt qua các cạnh và hợp nhất các tập hợp
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;

        std::cout << "Processing edge (" << u << ", " << v << "): ";
        // Kiểm tra xem u và v đã liên thông chưa
        if (!dsu.are_connected(u, v)) {
            // Nếu chưa, hợp nhất tập hợp của chúng
            dsu.unite(u, v);
            std::cout << "Uniting sets containing " << u << " and " << v << std::endl;
        } else {
            std::cout << u << " and " << v << " were already connected (in the same set)." << std::endl;
        }
    }

    std::cout << "\n--- Kết quả ---" << std::endl;

    // Đếm số lượng thành phần liên thông
    std::cout << "Number of connected components: " << dsu.count_sets() << std::endl; // Expected: 3 ({0,1,2}, {3,4}, {5})

    // Kiểm tra kết nối giữa các cặp đỉnh
    std::cout << "\nConnectivity checks:" << std::endl;
    std::cout << "Are 0 and 2 connected? " << (dsu.are_connected(0, 2) ? "Yes" : "No") << std::endl; // Expected: Yes
    std::cout << "Are 0 and 3 connected? " << (dsu.are_connected(0, 3) ? "Yes" : "No") << std::endl; // Expected: No
    std::cout << "Are 3 and 5 connected? " << (dsu.are_connected(3, 5) ? "Yes" : "No") << std::endl; // Expected: No
    std::cout << "Are 4 and 5 connected? " << (dsu.are_connected(4, 5) ? "Yes" : "No") << std::endl; // Expected: No
    std::cout << "Are 3 and 4 connected? " << (dsu.are_connected(3, 4) ? "Yes" : "No") << std::endl; // Expected: Yes

    // Kích thước của các tập hợp
    std::cout << "\nSet sizes:" << std::endl;
    std::cout << "Size of set containing 0: " << dsu.get_set_size(0) << std::endl; // Expected: 3
    std::cout << "Size of set containing 3: " << dsu.get_set_size(3) << std::endl; // Expected: 2
    std::cout << "Size of set containing 5: " << dsu.get_set_size(5) << std::endl; // Expected: 1


    return 0;
}

Giải thích Code:

• Chúng ta tạo một đối tượng DSU với 6 phần tử (đại diện cho 6 đỉnh của đồ thị). Ban đầu, mỗi đỉnh là một tập hợp riêng.
• Duyệt qua danh sách các cạnh. Với mỗi cạnh (u, v), ta kiểm tra xem đỉnh u và v đã nằm trong cùng một tập hợp (liên thông) hay chưa bằng dsu.are_connected(u, v).
• Nếu chúng chưa liên thông, ta gọi dsu.unite(u, v) để hợp nhất hai tập hợp chứa u và v.
• Sau khi xử lý hết tất cả các cạnh, số lượng tập hợp rời rạc còn lại trong DSU (dsu.count_sets()) chính là số lượng thành phần liên thông của đồ thị.
• Ta cũng có thể kiểm tra nhanh xem hai đỉnh bất kỳ có liên thông hay không bằng cách gọi dsu.are_connected().

Ví dụ minh họa 2: Phát hiện chu trình trong đồ thị vô hướng

Một ứng dụng quan trọng khác của DSU là phát hiện chu trình trong đồ thị vô hướng. Khi ta thêm một cạnh (u, v) vào đồ thị:

• Nếu u và v đã liên thông (đã cùng tập hợp trong DSU), thì việc thêm cạnh (u, v) sẽ tạo ra một chu trình.
• Nếu u và v chưa liên thông, việc thêm cạnh này chỉ đơn giản là kết nối hai thành phần liên thông khác nhau, ta hợp nhất tập hợp của chúng.

#include <iostream>
#include <vector>
#include <numeric>
#include <utility> // For std::pair

// Include the DSU class definition here
// class DSU { ... };

int main() {
    // Giả sử đồ thị có 5 đỉnh (0 đến 4)

    std::cout << "--- Ví dụ 2: Phát hiện chu trình ---" << std::endl;

    // Trường hợp 1: Đồ thị CÓ chu trình (0-1-2-3-4-0)
    int num_vertices_1 = 5;
    DSU dsu1(num_vertices_1);
    std::vector<std::pair<int, int>> edges_with_cycle = {
        {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 0} // Cạnh (4,0) tạo chu trình
    };

    bool cycle_found_1 = false;
    std::cout << "\nTesting graph with cycle (0-1-2-3-4-0):" << std::endl;
    for (const auto& edge : edges_with_cycle) {
        int u = edge.first;
        int v = edge.second;
        std::cout << "Processing edge (" << u << ", " << v << "): ";
        // Nếu u và v đã liên thông trước khi thêm cạnh (u,v)
        if (dsu1.are_connected(u, v)) {
            std::cout << "Nodes " << u << " and " << v << " are already in the same set. Cycle detected!" << std::endl;
            cycle_found_1 = true;
            // Không cần xử lý các cạnh tiếp theo nếu chỉ cần biết có chu trình hay không
            // break; // Uncomment if you want to stop after the first cycle
        } else {
            // Nếu chưa liên thông, hợp nhất chúng
            dsu1.unite(u, v);
            std::cout << "Uniting " << u << " and " << v << std::endl;
        }
    }
    if (!cycle_found_1) {
         std::cout << "No cycle found in this graph." << std::endl;
    }


    // Trường hợp 2: Đồ thị KHÔNG CÓ chu trình (một rừng cây)
    int num_vertices_2 = 6;
    DSU dsu2(num_vertices_2);
     std::vector<std::pair<int, int>> edges_without_cycle = {
        {0, 1}, {0, 2}, // Cây 1
        {3, 4},         // Cây 2
        // Đỉnh 5 cô lập
    };

    bool cycle_found_2 = false;
    std::cout << "\nTesting graph without cycle:" << std::endl;
     for (const auto& edge : edges_without_cycle) {
        int u = edge.first;
        int v = edge.second;
        std::cout << "Processing edge (" << u << ", " << v << "): ";
        if (dsu2.are_connected(u, v)) {
            std::cout << "Nodes " << u << " and " << v << " are already in the same set. Cycle detected!" << std::endl;
            cycle_found_2 = true;
            break;
        } else {
            dsu2.unite(u, v);
            std::cout << "Uniting " << u << " and " << v << std::endl;
        }
    }
     if (!cycle_found_2) {
         std::cout << "No cycle found in this graph." << std::endl;
    }


    return 0;
}

Giải thích Code:

• Đối với mỗi cạnh (u, v) trong đồ thị, trước khi thêm nó, ta kiểm tra xem u và v đã nằm trong cùng một tập hợp DSU hay chưa bằng dsu.are_connected(u, v).
• Nếu dsu.are_connected(u, v) trả về true, điều đó có nghĩa là đã có một đường đi từ u đến v tồn tại trong đồ thị (thông qua các cạnh đã xử lý trước đó). Việc thêm cạnh (u, v) lúc này sẽ tạo ra một chu trình. Ta có thể dừng lại và báo cáo đã phát hiện chu trình.
• Nếu dsu.are_connected(u, v) trả về false, nghĩa là u và v chưa liên thông. Thêm cạnh (u, v) chỉ đơn giản là kết nối hai thành phần riêng biệt. Ta gọi dsu.unite(u, v) để hợp nhất chúng.
• Nếu duyệt qua tất cả các cạnh mà không lần nào dsu.are_connected(u, v) trả về true trước khi unite, thì đồ thị không có chu trình.

Ví dụ minh họa 3: Ứng dụng trong Kruskal's MST Algorithm

DSU đóng vai trò then chốt trong giải thuật Kruskal để tìm cây bao trùm nhỏ nhất (MST). Kruskal hoạt động bằng cách duyệt qua các cạnh của đồ thị theo thứ tự trọng số tăng dần. Với mỗi cạnh (u, v):

• Nếu u và v chưa liên thông (kiểm tra bằng DSU are_connected(u, v)), thì việc thêm cạnh này vào tập hợp các cạnh của MST không tạo chu trình. Ta thêm cạnh này vào MST và hợp nhất tập hợp của u và v trong DSU (unite(u, v)).
• Nếu u và v đã liên thông, việc thêm cạnh này sẽ tạo chu trình, vì vậy ta bỏ qua cạnh này.

DSU giúp Kruskal kiểm tra điều kiện "không tạo chu trình" một cách rất nhanh chóng, cho phép thuật toán đạt hiệu quả cao.

(Lưu ý: Việc triển khai toàn bộ thuật toán Kruskal có thể khá dài, bao gồm cả việc sắp xếp cạnh. Ở đây chúng ta chỉ tập trung vào vai trò của DSU.)

#include <iostream>
#include <vector>
#include <numeric>
#include <utility>
#include <algorithm> // For std::sort

// Include the DSU class definition here
// class DSU { ... };

// Cấu trúc để lưu trữ cạnh (có trọng số)
struct Edge {
    int u, v, weight;
};

// Hàm so sánh để sắp xếp cạnh theo trọng số tăng dần
bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

int main() {
    std::cout << "--- Ví dụ 3: Ứng dụng trong Kruskal's MST (vai trò của DSU) ---" << std::endl;

    // Giả sử đồ thị có 4 đỉnh (0 đến 3) và các cạnh có trọng số
    int num_vertices = 4;
    std::vector<Edge> edges = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4} // Cạnh có trọng số nhỏ nhất
    };

    // Khởi tạo DSU
    DSU dsu(num_vertices);
    std::vector<Edge> mst_edges; // Danh sách các cạnh trong MST
    int mst_weight = 0;

    // 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(), compareEdges);

    std::cout << "Edges sorted by weight:" << std::endl;
    for(const auto& edge : edges) {
        std::cout << "(" << edge.u << ", " << edge.v << ", w=" << edge.weight << ") ";
    }
    std::cout << "\n" << std::endl;

    std::cout << "Processing edges for MST:" << std::endl;
    // Bước 2: Duyệt qua các cạnh đã sắp xếp
    for (const auto& edge : edges) {
        int u = edge.u;
        int v = edge.v;
        int weight = edge.weight;

        std::cout << "Considering edge (" << u << ", " << v << ", w=" << weight << "): ";

        // DSU check: If adding this edge does NOT create a cycle (u and v are in different sets)
        if (!dsu.are_connected(u, v)) {
            // Add the edge to MST
            mst_edges.push_back(edge);
            mst_weight += weight;

            // Unite the sets of u and v
            dsu.unite(u, v);

            std::cout << "Added to MST. Uniting " << u << " and " << v << "." << std::endl;
        } else {
            std::cout << "Creates a cycle. Skipping." << std::endl;
        }
    }

    std::cout << "\n--- Kết quả MST ---" << std::endl;
    std::cout << "Edges in MST:" << std::endl;
    for (const auto& edge : mst_edges) {
        std::cout << "(" << edge.u << ", " << edge.v << ", w=" << edge.weight << ") ";
    }
    std::cout << "\nTotal MST weight: " << mst_weight << std::endl; // Expected MST weight: 4 + 5 + 6 = 15 (Edges (2,3), (0,3), (0,2))

    return 0;
}

Giải thích Code:

• Chúng ta định nghĩa cấu trúc Edge để lưu đỉnh đầu, đỉnh cuối và trọng số.
• Sắp xếp các cạnh theo trọng số tăng dần.
• Duyệt qua các cạnh đã sắp xếp. Với mỗi cạnh (u, v), sử dụng dsu.are_connected(u, v) để kiểm tra xem u và v đã liên thông thông qua các cạnh đã chọn cho MST trước đó hay chưa.
• Nếu !dsu.are_connected(u, v) là true, nghĩa là thêm cạnh (u, v) không tạo chu trình. Cạnh này là một phần của MST. Ta thêm nó vào danh sách mst_edges, cộng trọng số của nó vào tổng trọng số MST, và gọi dsu.unite(u, v) để ghi nhận rằng bây giờ u và v (và các thành phần của chúng) đã liên thông.
• Nếu dsu.are_connected(u, v) là true, cạnh này sẽ tạo chu trình với các cạnh đã có trong MST, vì vậy ta bỏ qua nó.

Quá trình này tiếp tục cho đến khi ta đã xem xét tất cả các cạnh hoặc đã có N-1 cạnh trong MST (với N là số đỉnh), vì một cây bao trùm N đỉnh luôn có chính xác N-1 cạnh.

Bài tập ví dụ:

Thành phố và Lũ lụt

Trong một buổi đàm phán kinh doanh, FullHouse Dev được đối tác đưa ra một bài toán thú vị về việc quản lý các đế chế. Với kinh nghiệm trong việc xử lý các vấn đề phức tạp, nhóm đã bắt tay vào phân tích và giải quyết bài toán này.

Bài toán

Fatland là một thành phố bắt đầu với \(N\) đế chế khác nhau, được đánh số từ \(1\) đến \(N\). Theo thời gian, quân đội của một số đế chế đã chiếm đóng các đế chế khác. Mỗi lần chiếm đóng xảy ra khi quân đội của đế chế \(i\) xâm chiếm đế chế \(j\). Sau mỗi lần xâm chiếm, toàn bộ đế chế \(j\) trở thành một phần của đế chế \(i\), và đế chế \(j\) được đổi tên thành đế chế \(i\).

Hoàng đế Huang, người lãnh đạo Badland, muốn xâm chiếm Fatland. Để làm được điều này, ông ấy cần tính toán có bao nhiêu đế chế riêng biệt còn tồn tại ở Fatland sau tất cả các cuộc chiếm đóng.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\) - số lượng đế chế ban đầu ở Fatland.
• Dòng thứ hai chứa số nguyên \(K\) - số lượng cuộc chiếm đóng đã diễn ra.
• \(K\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(i\), \(j\), thể hiện quân đội của đế chế \(i\) đã chiếm đóng đế chế \(j\).

OUTPUT FORMAT:

• In ra một số nguyên duy nhất - số lượng đế chế còn tồn tại ở Fatland.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq K \leq 10^5\)

Ví dụ

INPUT

4
2
1 2
4 1

OUTPUT

2

Giải thích

Fatland ban đầu có các đế chế 1, 2, 3, 4. Đầu tiên, đế chế 1 xâm chiếm đế chế 2, vì vậy đế chế 2 được đổi tên thành đế chế 1. Sau đó, đế chế 4 xâm chiếm đế chế 1. Do đó, những gì ban đầu là đế chế 1 và 2 giờ đều được đổi tên thành đế chế 4. Hiện tại, chỉ còn đế chế 3 và 4 tồn tại, vì vậy câu trả lời là 2. Bài toán này mô tả quá trình sáp nhập các tập hợp (các đế chế). Khi đế chế i chiếm đế chế j, toàn bộ đế chế j (và bất kỳ đế chế nào mà j đã chiếm trước đó) trở thành một phần của đế chế i. Điều này ngụ ý rằng đế chế i trở thành "đại diện" mới cho tập hợp mà j từng thuộc về.

Cấu trúc dữ liệu phù hợp nhất để giải quyết bài toán này là Disjoint Set Union (DSU), còn được gọi là Union-Find.

Hướng giải chi tiết:

1. Khởi tạo: Tạo một cấu trúc DSU cho N phần tử (đế chế), đánh số từ 1 đến N. Ban đầu, mỗi đế chế là một tập hợp riêng biệt, và mỗi đế chế là đại diện (gốc) của chính nó.
2. Xử lý các cuộc chiếm đóng: Với mỗi cuộc chiếm đóng "i j":
   • Tìm đại diện (gốc) của đế chế i, gọi là root_i.
   • Tìm đại diện (gốc) của đế chế j, gọi là root_j.
   • Nếu root_i khác root_j, thực hiện thao tác Union để gộp tập hợp chứa j vào tập hợp chứa i. Cụ thể, đặt root_i làm cha của root_j. (Để tối ưu, có thể dùng Union theo rank hoặc size, nhưng về cơ bản là nối 2 gốc lại).
3. Tìm số lượng đế chế còn lại: Sau khi xử lý tất cả K cuộc chiếm đóng:
   • Số lượng đế chế còn lại chính là số lượng tập hợp rời rạc còn tồn tại trong cấu trúc DSU.
   • Để đếm số tập hợp, bạn có thể duyệt qua tất cả các đế chế ban đầu từ 1 đến N. Với mỗi đế chế k, tìm đại diện (gốc) của nó bằng thao tác Find (có sử dụng nén đường đi - path compression để tối ưu). Lưu trữ các đại diện duy nhất vào một tập hợp (ví dụ: std::set).
   • Kích thước của tập hợp chứa các đại diện duy nhất chính là số lượng đế chế còn lại.

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