Chương trình C++ triển khai Cấu trúc dữ liệu Tập hợp rời rạc (Disjoint Set)

Tập hợp rời rạc (Disjoint Set) là nhóm các tập hợp mà không phần tử nào thuộc về nhiều hơn một tập hợp. Nó hỗ trợ hai phép toán: Union (hợp) và Find (tìm) trên các tập con.

Find(): Tìm tập con chứa phần tử cụ thể và trả về đại diện của tập đó.

Union(): Gộp hai tập con khác nhau thành một tập con, đại diện của một tập trở thành đại diện của tập kia.

Các hàm và mã giả

Bắt đầu
  Giả sử k là phần tử
  makeset(k):
    k.parent = k.
  Find(x):
    Nếu k.parent == k
      trả về k.
    ngược lại
      trả về Find(k.parent)
  Union(a, b):
    Nhập hai tập a và b.
    aroot = Find(a)
    broot = Find(b)
    aroot.parent = broot
Kết thúc

Ví dụ mã nguồn

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class DisjointSet {
    // biểu diễn tập hợp rời rạc
    unordered_map<int, int> parent;
public:
    void makeSet(vector<int> const &wholeset) {
        // thực hiện makeset
        for (int i : wholeset) // tạo n tập rời rạc
            // (một cho mỗi phần tử)
            parent[i] = i;
    }
    int Find(int l) {
        // tìm gốc của tập chứa phần tử l
        if (parent[l] == l) // nếu l là gốc
            return l;
        return Find(parent[l]); // đệ quy tìm cha cho đến khi tìm thấy gốc
    }
    void Union(int m, int n) {
        // thực hiện Union của hai tập con m và n
        int x = Find(m);
        int y = Find(n);
        parent[x] = y;
    }
};

void print(vector<int> const &universe, DisjointSet &dis) {
    for (int i : universe)
        cout << dis.Find(i) << " ";
    cout << '\n';
}

int main() {
    vector<int> wholeset = { 6, 7, 1, 2, 3 }; // phần tử của tập toàn thể
    DisjointSet dis; // khởi tạo lớp DisjointSet
    dis.makeSet(wholeset); // tạo tập riêng cho từng phần tử
    dis.Union(7, 6); // 7, 6 cùng tập
    print(wholeset, dis);
    if (dis.Find(7) == dis.Find(6)) // cùng tập hay không
        cout << "Yes" << endl;
    else
        cout << "No";
    if (dis.Find(3) == dis.Find(4))
        cout << "Yes" << endl;
    else
        cout << "No";
    return 0;
}

Kết quả

6 6 1 2 3
Yes
No