Cấu trúc các tập không giao nhau – Disjoint Set Union (DSU)

Đỗ Thị Hồng Ngát 03/11/2023
03
Th11

Cấu trúc các tập không giao nhau – Disjoint Set Union (DSU)

1. Giới thiệu Disjoint Set Union

Disjoint Set Union (hay còn được gọi là DSU) là một kiểu cấu trúc dữ liệu được sử dụng nhiều trong các kỳ thi lập trình thi đấu. DSU được sử dụng vô cùng hiệu quả trong những bài tập liên quan đến quản lý tập hợp. DSU được liên tưởng giống như một rừng cây, và mỗi tập hợp chính là một cây con của khu rừng đó.

DSU gồm 2 thao tác cơ bản như sau:

  • Gộp 2 tập hợp \(A\) và \(B\) thành một tập hợp.
  • Tìm kiếm xem tập hợp nào chứa \(X\).

Dựa vào định nghĩa, ta có mã giả của cách cài đặt trâu của DSU như sau:

for (i = 1; i -> n; i++) 
    par[i] = i
    // với mọi nút i, thì i chính là cha của chính nó

int find(u) 
// tìm kiếm gốc của u
    nếu par[u] khác u
    // nếu u chưa phải là gốc của giá trị cần tìm
        return find(par[u])
        // đệ quy lên đỉnh cha
    return par[u]
    // nếu par[u] = u thì đó là gốc của giá trị cần tìm
    
void join(u, v) 
// gộp 2 tập hợp u, v thành 1 tập hợp
    u = find(u)
    v = find(v)
    // tìm kiếm gốc của u, v
    nếu u và v khác gốc thì par[v] = u

 

Để hình dung rõ hơn, mình sẽ lấy Bài toán 1 để mô tả cho cách cài đặt trên.

Mô tả thuật toán:

Coi tất cả các thùng nước làm một đỉnh của đồ thị.

  • Coi tất cả các đỉnh làm cha của chính nó.
  • Kiểm tra xem liệu \(1\) và \(2\) có cùng thuộc một đỉnh cha hay không. Dễ thấy, hàm \(find(1)\) trả về \(1\), \(find(2)\) trả về \(2\) nên tới thời điểm hiện tại, 2 đỉnh nhắc trên không thuộc cùng một tập hợp.
  • Nối tập hợp \(1\) – \(2\) vào một tập hợp lớn, đồ thị trở thành:
  • Ở bước này, ta sẽ gán đỉnh \(1\) là cha của đỉnh \(2\).
  • Dễ thấy, hàm \(find(3)\) trả về \(3\), \(find(7)\) trả về \(7\) nên tới thời điểm hiện tại, 2 đỉnh trên không thuộc cùng một tập hợp.
  • Nối tập hợp \(1\) – \(3\) vào một tập hợp lớn, đồ thị trở thành:Disjoint Set Union
  • Ở bước này, ta sẽ gán đỉnh \(2\) là cha của đỉnh \(3\).
  • Kiểm tra xem liệu \(1\) và \(3\) có thuộc cùng tập hợp hay không. Ta có: cha của đỉnh \(1\) là chính nó, nên gốc sẽ là \(1\). Cha của đỉnh \(2\) là đỉnh \(1\), và cha của đỉnh \(1\) là chính nó, nên gốc sẽ là \(1\). Do 2 đỉnh \(1\) – \(3\) chung gốc, nên 2 thùng nước thông nhau.
  • …

→ Dễ thấy, với cách cài đặt này, độ phức tạp của thuật toán sẽ là \(O(n)\). Đây là độ phức tạp không thể chấp nhận được, do những bài toán liên quan tới DSU thường rơi vào khoảng \((n, q ≤ 10^5)\). Chính vì vậy, ta buộc phải cải tiến thuật toán trên để giúp độ phức tạp chỉ còn \(O(log(n))\).

Ta sẽ tối ưu hóa thuật toán như sau: Ta sẽ luôn đặt gốc của cây có kích cỡ lớn hơn làm cha của cây có kích cỡ nhỏ hơn. Mặt khác, ở thao tác tìm gốc của \(u\), ta sẽ gán cha của tất cả các đỉnh trở trên đường đi về đỉnh gốc thay vì chỉ đệ quy thẳng lên đỉnh cha.

Ta có mã giả của thuật toán cải tiến như sau:

for (i = 1; i -> n; i++) 
    par[i] = i
    // với mọi nút i, thì i chính là cha của chính nó

int find(u) 
// tìm kiếm gốc của u
    nếu par[u] khác u
    // nếu u chưa phải là gốc của giá trị cần tìm
        return find(par[u])
        // đệ quy lên đỉnh cha
    return par[u]
    // nếu par[u] = u thì đó là gốc của giá trị cần tìm
    
void join(u, v) 
// gộp 2 tập hợp u, v thành 1 tập hợp
    u = find(u)
    v = find(v)
    // tìm kiếm gốc của u, v
    nếu u và v khác gốc thì par[v] = u

 

→ Độ phức tạp thời gian: \(O(log(n))\)

2. Bài toán 1

Nguồn bài: Các thùng nước – VNOI
Cho \(N\) \((N ≤ 10000)\) thùng nước đánh số từ \(1\) đến \(N\), giữa \(2\) thùng bất kỳ đều có một ống nối có một van có thể khóa hoặc mở. Ở trạng thái ban đầu tất cả các van đều đóng.

Bạn được cho một số yêu cầu, trong đó mỗi yêu cầu có \(2\) dạng:

  • Dạng \(X\) \(Y\) \(1\) có ý nghĩa là bạn cần mở van nối giữa 2 thùng nước \(X\) và \(Y\).
  • Dạng \(X\) \(Y\) \(2\) có ý nghĩa là bạn cần cho biết với trạng thái các van đang mở / khóa như hiện tại thì 2 thùng \(X\) và \(Y\) có thuộc cùng một nhóm bình thông nhau hay không? Hai thùng được coi là thuộc cùng một nhóm bình thông nhau nếu nước từ bình này có thể chảy đến được bình kia qua một số ông có van đang mở.

Input

  • Dòng đầu tiên ghi một số nguyên dương \(P\) \((P ≤ 50000)\) là số yêu cầu.
  • Trong \(P\) dòng tiếp theo, mỗi dòng ghi ba số nguyên dương \(X\) \(Y\) \(Z\) với ý nghĩa có yêu cầu loại \(Z\) với 2 thùng nước \(X\) và \(Y\).

Output

  • Với mỗi yêu cầu dạng \(X\) \(Y\) \(2\) (với \(Z\) \(=\) \(2\)) bạn cần ghi ra số \(0\) hoặc \(1\) trên \(1\) dòng tùy thuộc \(2\) thùng \(X\) và \(Y\) không thuộc hoặc thuộc cùng một nhóm bình.

Sample Input

9
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2

Sample Output

0
0
1
0
1
0

Phân tích bài toán:

  • Dựa vào phần mở đầu, ta có thể thấy rằng đây chính là bài tập DSU điển hình.
  • Thao tác mở van nối giữa 2 thùng nước – chính là việc ta gộp 2 tập hợp vào làm 1. Bên cạnh đó, để kiểm tra việc 2 thùng nước \(A\) và \(B\) bất kỳ có thông nhau hay không – tức là ta sẽ kiểm tra xem liệu \(A\) và \(B\) có chung đỉnh gốc hay không. Nếu có, \(A\) và \(B\) sẽ cùng thuộc một tập hợp (tức là thông nhau) và ngược lại.

Code mẫu:

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e4 + 2;

int sz[N + 5], par[N + 5];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        par[i] = i;
    }
}

int find(int u) {
    if (par[u] == u) {
        return u;
    }
    return par[u] = find(par[u]);
}

void join(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) {
        return;
    }
    if (sz[u] < sz[v]) {
        swap(u, v);
    }
    sz[u] += sz[v];
    par[v] = u;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int p; cin >> p;
    init(N);
    while (p--) {
        int u, v, type; 
        cin >> u >> v >> type;
        if (type == 1) {
            join(u, v);
            continue;
        }
        if (find(u) == find(v)) {
            cout << 1;
        } else {
            cout << 0;
        }
        cout << "\n";
    }
    return 0;
}

3. Bài toán 2

Cho đồ thị vô hướng \(n\) đỉnh, \(n – 1\) cạnh. Mỗi thao tác bao gồm xóa và thêm 1 cạnh. Hỏi cần bao nhiêu thao tác để đồ thị liên thông và liệt kê các thao tác đó ra.

Input

  • Dòng đầu tiên ghi số \(n\) \((n ≤ 10000)\).
  • \(n – 1\) dòng tiếp theo, ghi \(u\), \(v\) tức là tồn tại cạnh \(u – v\) trên đồ thị.

Output

  • Dòng đầu tiên ghi \(t\) là số thao tác để đồ thị liên thông.
  • \(t\) dòng tiếp theo, mỗi dòng ghi 4 số nguyên \(i\) \(j\) \(u\) \(v\) nghĩa là cạnh \(i\) – \(j\) sẽ được thêm và cạnh \(u\) – \(v\) vào bị xóa đi.

Sample Input

6
1 2
2 3
1 4
5 6
3 4

 

Sample Output

1
1 5 3 4

 

Phân tích bài toán:

  • Nhận xét: Trước khi cho cạnh \(u\) – \(v\) vào đồ thị, nếu đỉnh \(u\) và \(v\) chung gốc, thì cạnh \(u\) – \(v\) sẽ là cạnh cần xóa đi khỏi đồ thị. Nếu không, ta sẽ gộp \(u\) và \(v\) thành một tập hợp bằng cách sử dụng DSU.
  • Sau đó, ta sẽ kiểm tra xem gốc của từng đỉnh có giá trị bằng chính nó hay không. Nếu có, lưu hết vào một vector và các cạnh cần thêm sẽ có đỉnh là 2 phần tử liền nhau ở vector đó.

Code mẫu:

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 2;

#define int long long

int sz[N + 5], par[N + 5];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        par[i] = i;
    }
}

int find(int u) {
    if (par[u] == u) {
        return u;
    }
    return par[u] = find(par[u]);
}

void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) {
        return;
    }
    if (sz[u] < sz[v]) {
        swap(u, v);
    }
    sz[u] += sz[v];
    par[v] = u;
}

#define pii pair<int, int>

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<pii> deleted, added;
    vector<int> marked;
    init(n);
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        if (find(u) == find(v)) {
            deleted.push_back({u, v});
        } else {
            join(u, v);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (find(i) == i) {
            marked.push_back(i);
        }
    }
    for (int i = 0; i < marked.size() - 1; i++) {
        added.push_back({marked[i], marked[i + 1]});
    }
    cout << deleted.size() << '\n';
    for (int i = 0; i < added.size(); i++) {
        cout << added[i].first << " " << added[i].second << " ";
        cout << deleted[i].first << " " << deleted[i].second << '\n';

    }
    return 0;
}

4. Khi nào sử dụng DSU?

DSU được sử dụng nhiều trong các kỳ thi liên quan tới lập trình thi đấu. Những ứng dụng tiêu biểu nhất của DSU có thể kể đến như:

  • Quản lý tập hợp
  • Bài toán xếp hàng
  • Đồ thị 2 phía
  • Liên thông mạnh
  • Small to large

5. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Advanced của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Unable to display PDF file. Download instead. 

ÁP DỤNG GIẢI BÀI TOÁN BITMAP

Phân tích bài toán:

  • Nhận xét: Sử dụng DFS thông thường cho bài này sẽ bị TLE do mỗi lần update, ta phải đi DFS lại 1 lần để tìm thành phần liên thông lớn nhất. Để giải quyết được hiệu quả vấn đề này, ta nghĩ đến việc sử dụng CTDL DSU. Trước khi bắt đầu truy vấn, cần DSU một lần thì các thao tác sau mới update được. Kết quả bài toán chính là kích thước của tập hợp lớn nhất tính tới thời điểm hiện tại.

Code mẫu:

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 2;

#define pii pair<int, int>
#define int long long
#define inf 1e18

const int hx[4] = {-1, 0, 0, 1};
const int hy[4] = {0, -1, 1, 0};

pii par[N][N];
int sz[N][N], a[N][N];
bool marked[N][N];

int getmax = -inf;

void init(int m, int n) {
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            par[i][j] = {i, j};
            sz[i][j] = 1;
        }
    }    
}

pii find(int u, int v) {
    if (par[u][v] == make_pair(u, v)) {
        return make_pair(u, v);
    }
    return par[u][v] = find(par[u][v].first, par[u][v].second);
}

void join(pii &u, pii &v) {
    u = find(u.first, u.second);
    v = find(v.first, v.second);
    if (u == v) {
        return;
    }
    if (sz[u.first][u.second] < sz[v.first][v.second]) {
        swap(u, v);
    }
    par[v.first][v.second] = u;
    sz[u.first][u.second] += sz[v.first][v.second];
    getmax = max(getmax, sz[u.first][u.second]);
}

int n, m;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    init(m, n);
    memset(marked, false, sizeof marked);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k < 4; k++) {
            	int dx = i + hx[k];
            	int dy = j + hy[k];
            	if (a[dx][dy] == 1 && a[i][j] == 1) {
            		pii A = make_pair(i, j);
            		pii B = make_pair(dx, dy);
            		join(A, B);
            	}
            }
        }
    }
    int q; cin >> q;
    while (q--) {
        int x, y; cin >> x >> y;
        a[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int dx = x + hx[i];
            int dy = y + hy[i];
            if (a[dx][dy] == 1) {
                pii a = make_pair(dx, dy), b = make_pair(x, y);
                join(a, b);
            }
        }
    	cout << getmax << '\n';
    }
}

 

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *