Hiểu bài toán

Bài toán yêu cầu xử lý một chuỗi các truy vấn trên một đồ thị người dùng có thể thêm cạnh hoặc kiểm tra tính liên thông. Ban đầu đồ thị có N đỉnh (1 ≤ N ≤ 10000) và không có cạnh. Có hai loại truy vấn:

1. X Y 1: Thêm cạnh nối X và Y.
2. X Y 2: Kiểm tra xem X và Y có thuộc cùng một thành phần liên thông không. Nếu có in ra 1, ngược lại in ra 0.

Số lượng truy vấn P tối đa là 50000. Sử dụng cấu trúc dữ liệu Disjoint Set Union (DSU) hoặc Union-Find để quản lý các tập hợp liên thông một cách hiệu quả.

Các cách tiếp cận

Cách BFS/DFS để kiểm tra liên thông

void solve() {
    int N;
    cin >> N;
    vector<vector<int>> adj(N + 1);
    vector<bool> visited(N + 1);

    while(N--) {
        int u, v, type;
        cin >> u >> v >> type;
        if(type == 1) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        } else {
            // Reset visited
            fill(visited.begin(), visited.end(), false);
            queue<int> q;
            q.push(u);
            visited[u] = true;
            bool connected = false;

            while(!q.empty()) {
                int curr = q.front(); q.pop();
                if(curr == v) {
                    connected = true;
                    break;
                }
                for(int neighbor : adj[curr]) {
                    if(!visited[neighbor]) {
                        visited[neighbor] = true;
                        q.push(neighbor);
                    }
                }
            }
            cout << (connected ? 1 : 0) << "\n";
        }
    }
}

• Time Complexity: O(P * N) ~ 50000 * 10000 = 5*10^8 operations, Time Limit Exceeded
• Space Complexity: O(N)

Cách tiếp cận này sử dụng danh sách kề để lưu đồ thị. Với mỗi truy vấn loại 2, ta thực hiện BFS hoặc DFS để kiểm tra đường đi từ X đến Y. Mặc dù đơn giản, cách này quá chậm vì với mỗi truy vấn kiểm tra, ta có thể phải duyệt toàn bộ đồ thị (O(N + E)). Với P lớn, độ phức tạp sẽ là O(P*(N+E)) không thể chấp nhận được.

Cách Disjoint Set Union (DSU) cơ bản

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

int parent[10005];

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        parent[b] = a;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int P;
    if (cin >> P) {
        for(int i = 1; i <= 10000; i++) parent[i] = i;
        while (P--) {
            int x, y, z;
            cin >> x >> y >> z;
            if (z == 1) {
                union_sets(x, y);
            } else {
                cout << (find_set(x) == find_set(y) ? 1 : 0) << "\n";
            }
        }
    }
    return 0;
}

• Time Complexity: O(P * α(N)) ~ O(P)
• Space Complexity: O(N)

DSU là cấu trúc dữ liệu tối ưu cho bài toán này. Mảng parent lưu cha của mỗi nút. find_set tìm đại diện của tập hợp (gốc) với đệ quy có nén đường dẫn (path compression). union_sets hợp nhất hai tập hợp.

• Khởi tạo: Gán parent[i] = i cho mọi i.
• Truy vấn 1: Gọi union_sets(x, y).
• Truy vấn 2: Kiểm tra find_set(x) == find_set(y). Độ phức tạp trung bình là xấp xỉ tuyến tính (Inverse Ackermann function), rất nhanh.

Cách DSU với Union by Rank (Optimized)

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

struct DSU {
    vector<int> parent, rank;
    DSU(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for(int i = 1; i <= n; i++) parent[i] = i;
    }

    int find_set(int v) {
        if (v == parent[v]) return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (rank[a] < rank[b]) swap(a, b);
            parent[b] = a;
            if (rank[a] == rank[b]) rank[a]++;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int P;
    if (cin >> P) {
        DSU dsu(10000);
        while(P--) {
            int x, y, z;
            cin >> x >> y >> z;
            if (z == 1) dsu.union_sets(x, y);
            else cout << (dsu.find_set(x) == dsu.find_set(y) ? 1 : 0) << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(P * α(N))
• Space Complexity: O(N)

Đây là phiên bản DSU chuẩn mực nhất, kết hợp cả hai tối ưu:

1. Path Compression (Nén đường dẫn) trong find_set.
2. Union by Rank (Hợp theo cấp bậc) trong union_sets. Biến rank ước lượng độ sâu của cây. Khi hợp nhất, ta gắn cây có cấp bậc nhỏ hơn vào gốc của cây có cấp bậc lớn hơn để tránh cây bị sâu quá mức. Các giải pháp trong bài tham khảo đều sử dụng biến thể này hoặc biến thể của nó (ví dụ Solution 2).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán là bài toán kinh điển về quản lý tập hợp liên thông, phù hợp nhất với DSU.
• Cần xử lý input/output nhanh (ios::syncwithstdio(0); cin.tie(0);) để tránh trễ do nhập xuất.
• DSU trung bình có độ phức tạp rất tốt (gần như tuyến tính), đủ để xử lý 50000 truy vấn trong thời gian giới hạn.

Lỗi thường gặp

• Quên khởi tạo parent cho các đỉnh từ 1 đến N trước khi xử lý truy vấn.
• Sử dụng DFS/BFS cho mỗi truy vấn loại 2 dẫn đến Time Limit Exceeded.
• Lỗi truy cập mảng超出界 (out of bounds) nếu khai báo mảng parent quá nhỏ so với giá trị đỉnh cho phép (problem giới hạn N ≤ 10000, nhưng code mẫu Solution 1 khai báo 1000005 - điều này không sai nhưng cần lưu ý đề bài).
• Quên in kết quả theo format mỗi dòng một số cho truy vấn loại 2.