Hướng giải của Số lượng thành phần liên thông (Olympic 30/4 K11 - 2023) - ACOJ: Trung tâm Accept

Hướng giải của Số lượng thành phần liên thông (Olympic 30/4 K11 - 2023)

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Để giải bài này, đơn giản là dựng danh sách kề cho đồ thị $B$ , sau đó dùng DFS để tìm số lượng các thành phần liên thông và độ lớn của chúng.

Tuy nhiên, phương pháp này sẽ làm tràn bộ nhớ, vì cho rằng $N = M = 100000$ thì sẽ có $N \times M$ trong đồ thị $B$ . Cũng vì vậy, với $N + M$ nhỏ hơn hoặc bằng $200000$ nhưng số cạnh là $N \times (N - 1) / 2 - M$ trong $B$ , số lượng cạnh dễ dàng vượt quá $10^{8}$ , số lượng cạnh như vậy phương pháp DFS bình thường sẽ bị quá thời gian.

Giải pháp $1$ :

Dùng một tập hợp để lưu giữ các đỉnh chưa viếng thăm.
Với mỗi đỉnh từ $1$ đến $N$ , thực hiện DFS nếu nó chưa được viếng thăm, khi thực hiện DFS ta sẽ gỡ bỏ đỉnh này ra khỏi các đỉnh chưa viếng thăm. Trong hàm DFS, ta sẽ dò trên các đỉnh chưa viếng thăm còn lại bằng cách dùng hàm upper_bound.
Gọi $u$ là đỉnh hiện tại của hàm DFS.
Lặp lại trên các đỉnh chưa viếng thăm, gọi đỉnh này là $v$ .
Với các đỉnh $v$ đó, nếu có cạnh $(u, v)$ tồn tại trong $A$ , ta sẽ viếng thăm $v$ và gỡ nó ra khỏi các đỉnh chưa viếng thăm.

Giải pháp $2$ :

Chọn những đỉnh có bậc lớn hơn $n / 2$ trong đồ thị $B$ .
Một quy luật là bất kỳ hai đỉnh nào như trên đều nằm trong cùng một thành phần liên thông.
Lý do: Với $2$ đỉnh bất kỳ có bậc lớn hơn $n / 2$ , sẽ tồn tại một đỉnh thứ ba mà đỉnh này sẽ có cạnh nối đến $2$ đỉnh kia.
Với những đỉnh có bậc nhỏ hơn hoặc bằng $n / 2$ , ta có thể dùng phương pháp DFS bình thường hoặc DSU. Tổng bậc của tất cả các đỉnh đó là nhỏ hơn $n$ , vì vậy dùng DFS bình thường trên các đỉnh đó sẽ không vượt quá thời gian quy định.

Sao chép

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

const int MAXN = 2e5 + 5;

vector<int> adj[MAXN];   // danh sách kề của đồ thị gốc A
bool visited[MAXN];      // đánh dấu đỉnh đã duyệt
int next_[MAXN], prev_[MAXN];
vector<int> component;   // thành phần liên thông đang xét

void bfs(int start, int n) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    component.push_back(start);

    if (prev_[start] != -1) next_[prev_[start]] = next_[start];
    if (next_[start] != -1) prev_[next_[start]] = prev_[start];

    while (!q.empty()) {
        int u = q.front(); q.pop();

        vector<int> to_add;
        for (int v = next_[0]; v != -1 && v <= n; v = next_[v]) {
            if (!binary_search(adj[u].begin(), adj[u].end(), v)) {
                to_add.push_back(v);
            }
        }

        for (int v : to_add) {
            if (!visited[v]) {
                visited[v] = true;
                component.push_back(v);
                q.push(v);

                if (prev_[v] != -1) next_[prev_[v]] = next_[v];
                if (next_[v] != -1) prev_[next_[v]] = prev_[v];
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;

        // Khởi tạo
        for (int i = 1; i <= n; ++i) {
            adj[i].clear();
            visited[i] = false;
        }

        // Nhập cạnh của đồ thị A
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        // Sắp xếp danh sách kề để dùng binary_search
        for (int i = 1; i <= n; ++i)
            sort(adj[i].begin(), adj[i].end());

        // Khởi tạo danh sách liên kết các đỉnh chưa duyệt
        for (int i = 0; i <= n + 1; ++i)
            next_[i] = prev_[i] = -1;

        next_[0] = 1;
        prev_[1] = 0;
        for (int i = 1; i <= n; ++i) {
            next_[i] = i + 1;
            prev_[i] = i - 1;
        }
        next_[n] = -1;

        // Tìm các thành phần liên thông trong đồ thị B
        vector<int> sizes;
        for (int u = next_[0]; u != -1 && u <= n; u = next_[0]) {
            if (!visited[u]) {
                component.clear();
                bfs(u, n);
                sizes.push_back(component.size());
            }
        }

        // Xuất kết quả
        sort(sizes.begin(), sizes.end());
        cout << sizes.size() << '\n';
        for (int sz : sizes) cout << sz << ' ';
        cout << '\n';
    }

    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.