Giải thích bài tập SP5150

Đề bài

Bài gốc tại trang web SPOJ.

Kiến thức tiên quyết

1. Cấu trúc dữ liệu Disjoint Set (Union-Find).
2. Tài khoản SPOJ.

Hướng giải quyết

Bài toán này dễ dàng nhận ra cần sử dụng cấu trúc Disjoint Set. (Nếu chưa biết thì xem phần kết luận cuối bài.)

Với mỗi đỉnh \(i\), ta có thể trực tiếp thiết lập \(parent_i\) là cha của \(i\). (Cha của chính nó nếu là gốc.)

Tiếp theo là thao tác kiểm tra tập hợp mà một phần tử thuộc về. (Đây là thao tác cơ bản.)

long long find(long long x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]); // Nén đường đi, cập nhật cha thành đại diện.
}

Tiếp đến, việc hợp nhất hai tập hợp cũng rất đơn giản, không có gì phức tạp.

Chỉ cần đặt gốc của cây chứa \(x\) trở thành con của gốc cây chứa \(y\).

void unite(long long x, long long y) {
    parent[find(x)] = find(y);
}

Sau đó là bước khởi tạo. Khi có thao tác xóa, ta cần khái niệm "đỉnh giả". Các đỉnh từ \(0, 1, 2, ..., n-1\) là đỉnh thật, các đỉnh từ \(n, n+1, n+2, ..., 2n-1\) là đỉnh giả, và các đỉnh từ \(2n, 2n+1, ..., 2n+m\) dùng để đếm số lượng đỉnh đã bị xóa.

void init(long long n, long long m) {
    current_count = 2 * n;
    result = 0;
    for(int i = 0; i < n; i++) parent[i] = n + i;
    for(int i = n; i <= current_count + m; i++) parent[i] = i;
    memset(is_deleted, 0, sizeof(is_deleted));
}

Việc xóa chỉ đơn giản là thay đổi cha của đỉnh đó sang một đỉnh mới, làm cho nó tách rời khỏi các đỉnh khác.

void remove(int x){
    parent[x] = current_count++;
}

Trong đó current_count là tổng số đỉnh đã được sử dụng.

Mã nguồn

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> 
using namespace std;
const int MAX_N=10000005;
long long parent[MAX_N], is_deleted[MAX_N], current_count, result, n, m, x, y;
//parent[i] lưu cha của đỉnh i.
char operation;
void init(long long n, long long m) {
    current_count = 2 * n;
    result = 0;
    for(int i = 0; i < n; i++) parent[i] = n + i;
    for(int i = n; i <= current_count + m; i++) parent[i] = i;
    memset(is_deleted, 0, sizeof(is_deleted));
}
long long find(long long x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]); // Nén đường đi.
}
void unite(long long x, long long y) {
    parent[find(x)] = find(y); // Đặt gốc của x làm con của gốc của y.
}
void remove(int x){
    parent[x] = current_count++;
}
int main(){
    long long case_number = 0;
    while(1){
        scanf("%lld %lld", &n, &m);
        if(!n && !m) break; // Kết thúc khi cả hai số đều bằng 0.
        init(n, m); // Khởi tạo
        case_number++;
        while(m--){
            cin >> operation;
            if(operation == 'M'){
                scanf("%lld %lld", &x, &y);
                unite(x, y); // Hợp nhất.
            } else {
                scanf("%lld", &x);
                remove(x); // Xóa đỉnh.
            }
        }
        for(int k = 0; k < n; k++){
            int representative = find(k);
            if(!is_deleted[representative]) result++, is_deleted[representative] = 1;
        }
        printf("Case #%lld: %lld\n", case_number, result);
    }
    return 0;
}

Gợi ý hoàn chỉnh

Nếu bạn như tôi và bạn tôi từng gặp khó khăn với việc không thể đăng ký tài khoản SPOJ, hãy nhấn vào liên kết sau để theo hướng dẫn đăng ký.

Tổng kết

1. Chỉ số bắt đầu từ \(0\) đến \(n-1\), không nhầm lẫn. (Bạn tôi từng sai điều này.)
2. Cần có tài khoản SPOJ. (Từ 50 lần thất bại và sự tuyệt vọng sau đó.)
3. Các thuật toán cơ bản của Disjoint Set và khả năng xóa đỉnh đơn lẻ.

Phụ lục (Ghi chú học tập về Disjoint Set)

Định nghĩa (Chức năng)

Disjoint Set là cấu trúc dữ liệu giúp duy trì nhiều tập hợp không chồng chéo và hỗ trợ hợp nhất và truy vấn hiệu quả.

Tư duy thực hiện

Có thể tưởng tượng cấu trúc dưới dạng cây, trong đó gốc của mỗi cây đại diện cho tập hợp.

Ta dùng mảng parent để lưu cha của mỗi đỉnh. Trong quá trình truy vấn, nếu \(x\) là gốc thì nó là đại diện, ngược lại đệ quy tìm cha cho đến khi đến gốc.

Khi hợp nhất hai tập hợp, ta đặt cha của gốc \(x\) là gốc \(y\).

Tuy nhiên, cách làm trên có độ phức tạp thời gian cao, nên cần tối ưu hóa bằng nén đường đi hoặc hợp nhất theo cấp bậc. (Ở đây chỉ nói đến nén đường đi vì phổ biến.)

Thực tế rất đơn giản: Khi truy vấn, tất cả các đỉnh trên đường đi đều được trực tiếp liên kết đến gốc. Vì ta chỉ quan tâm đến gốc của mỗi tập hợp, không phải hình dạng cụ thể.

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

Mã nguồn triển khai

1. Khởi tạo:

Mỗi phần tử tạo thành một tập hợp riêng biệt, tương ứng với một cây có 1 đỉnh. Gán cha của mỗi đỉnh là chính nó.

for(int i = 1; i <= n; i++) parent[i] = i;

2. Thao tác tìm kiếm:

Nếu \(x\) là gốc, trả về \(x\). Ngược lại, đệ quy tìm cha cho đến khi gặp gốc.

long long find(long long x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]); // Nén đường đi.
}

3. Thao tác hợp nhất:

Đặt gốc của \(x\) làm con của gốc của \(y\).

void unite(long long x, long long y) {
    parent[find(x)] = find(y); // Đặt gốc của x làm con của gốc của y.
}

Vậy là bạn đã hiểu rồi đúng không? Hãy quay lại đọc lại bài toán trên nhé.

Bài tập gợi ý về Disjoint Set

1. P3367 [Template] Disjoint Set (Bắt buộc phải nắm)
2. [NOI2002] Legend of Galactic Heroes (Disjoint Set có trọng số)
3. [NOI2001] Food Chain (Disjoint Set có trọng số)
4. UVA11987 Almost Union-Find (Xóa đỉnh đơn lẻ trong Disjoint Set có trọng số)