Bài 21.3: Khái niệm và cách xác định khớp trong đồ thị

Chào mừng các bạn trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ khám phá một khái niệm đặc biệt trong lý thuyết đồ thị: khớp, hay còn gọi là cầu (bridge). Khái niệm này cực kỳ quan trọng trong việc phân tích tính kết nối và sự "vững chắc" của một mạng lưới.

Hãy tưởng tượng bạn có một mạng lưới các thành phố được nối với nhau bằng các con đường. Nếu một con đường nào đó bị hỏng, liệu hai thành phố trước đó có còn liên lạc được với nhau không? Nếu việc hỏng con đường đó làm tăng số lượng các "phần độc lập" trong mạng lưới (tức là tách mạng lưới thành nhiều mảnh rời rạc hơn), thì con đường đó chính là một khớp.

Khái niệm Khớp (Bridge) trong Đồ thị

Một khớp (hoặc cầu) trong một đồ thị vô hướng, liên thông là một cạnh mà khi loại bỏ cạnh này ra khỏi đồ thị, thì số lượng các thành phần liên thông (connected components) của đồ thị sẽ tăng lên.

Nói cách khác, một cạnh (u, v) là khớp nếu việc xóa nó làm cho đỉnh u và đỉnh v không còn đường đi nào nối trực tiếp hoặc gián tiếp với nhau nữa.

Tại sao khái niệm này quan trọng?

Trong mạng máy tính: Khớp có thể là một liên kết cáp quang quan trọng mà nếu bị đứt sẽ chia tách mạng thành nhiều phần.
Trong mạng lưới giao thông: Khớp là một con đường chiến lược mà nếu bị tắc nghẽn hoặc hỏng sẽ gây ách tắc nghiêm trọng hoặc cô lập một khu vực.
Trong phân tích mạng xã hội: Khớp có thể là một mối quan hệ cá nhân hoặc một cầu nối giữa hai nhóm người, việc mất đi mối quan hệ này có thể chia rẽ cộng đồng.

Việc xác định các khớp giúp chúng ta nhận diện những "điểm yếu" hoặc những liên kết quan trọng sống còn trong cấu trúc mạng lưới.

Cách xác định Khớp trong Đồ thị

Làm thế nào để tìm ra các khớp trong một đồ thị?

Phương pháp "Ngây thơ" (Naive Approach)

Cách đơn giản nhất để tìm khớp là thử lần lượt từng cạnh:

Lấy một cạnh (u, v).
Tạm thời xóa cạnh này khỏi đồ thị.
Kiểm tra xem đỉnh u và v còn liên thông với nhau không (ví dụ, dùng BFS hoặc DFS để xem có thể đi từ u đến v không).
Nếu u và v không còn liên thông, thì (u, v) là một khớp.
Đưa cạnh (u, v) trở lại đồ thị và lặp lại cho cạnh khác.

Phương pháp này hoạt động đúng, nhưng lại không hiệu quả về mặt thời gian. Giả sử đồ thị có V đỉnh và E cạnh. Với mỗi cạnh, chúng ta thực hiện một lần kiểm tra liên thông (BFS/DFS), mất O(V+E) thời gian. Tổng cộng, độ phức tạp của phương pháp này là O(E * (V+E)). Đối với đồ thị lớn, phương pháp này rất chậm.

Phương pháp hiệu quả: Dựa trên Duyệt đồ thị theo chiều sâu (DFS)

Cách hiệu quả hơn để tìm khớp là sử dụng một biến thể của thuật toán DFS. Thuật toán này dựa trên việc theo dõi thời gian thăm (discovery time) và thời gian thăm sớm nhất có thể quay lại (lowest reachable ancestor time) từ một đỉnh hoặc tập hợp các đỉnh con.

Chúng ta sẽ sử dụng hai mảng (hoặc vector):

disc[u] (discovery time): Thời điểm (bước thời gian) mà đỉnh u được thăm lần đầu tiên trong quá trình DFS.
low[u] (lowest reachable time): Thời điểm thăm sớm nhất (disc) của đỉnh nào đó có thể đạt được từ đỉnh u (bao gồm cả u) thông qua các cạnh cây (tree edges) của cây DFS hoặc thông qua nhiều nhất một cạnh ngược (back edge).

Ý tưởng chính: Khi ta duyệt DFS từ u đến v (trong đó v là con của u trong cây DFS), nếu low[v] > disc[u], điều đó có nghĩa là v và tất cả các đỉnh trong cây con gốc v không có cách nào để quay lại u hoặc bất kỳ tổ tiên nào của u trong cây DFS, ngoại trừ thông qua cạnh (u, v). Do đó, nếu ta xóa cạnh (u, v), cây con gốc v sẽ bị tách rời khỏi phần còn lại của đồ thị. Cạnh (u, v) chính là một khớp.

Cách tính disc và low trong quá trình DFS:

Duyệt DFS từ một đỉnh bất kỳ (ví dụ, đỉnh 0). Sử dụng một biến timer để theo dõi thời gian.
Khi thăm một đỉnh u lần đầu tiên:
- Đánh dấu u đã được thăm (visited).
- Gán disc[u] = low[u] = timer.
- Tăng timer lên 1.
Duyệt qua tất cả các đỉnh kề v của u.
- Nếu v là đỉnh cha của u trong cây DFS (để tránh xử lý cạnh quay về cha như cạnh ngược thông thường), bỏ qua.
- Nếu v đã được thăm: Điều này có nghĩa là (u, v) là một cạnh ngược. Ta có thể đi từ u đến v và v đã được thăm trước u. Thời điểm thăm của v là disc[v]. Cập nhật low[u] = min(low[u], disc[v]). Điều này phản ánh rằng từ u, ta có thể đi đến một đỉnh có thời gian thăm là disc[v] thông qua cạnh ngược (u, v).
- Nếu v chưa được thăm: Điều này có nghĩa là (u, v) là một cạnh cây. Thực hiện đệ quy DFS cho v (với u là cha của v): DFS(v, u, ...). Sau khi cuộc gọi đệ quy trả về, ta đã tính toán xong low[v]. Cập nhật low[u] = min(low[u], low[v]). Điều này có nghĩa là thời điểm thăm sớm nhất có thể quay lại từ u là nhỏ nhất trong số low[u] ban đầu và low[v] (vì từ u ta có thể đi đến bất kỳ đỉnh nào trong cây con của v thông qua cạnh (u, v)).
- Kiểm tra khớp: Sau khi cập nhật low[u] từ cây con của v (tức là sau khi cuộc gọi đệ quy DFS(v, u, ...) trả về), nếu low[v] > disc[u], thì cạnh (u, v) là một khớp. Thêm cặp (u, v) vào danh sách các khớp tìm được.

Quá trình DFS cần được bắt đầu từ mọi đỉnh chưa thăm để đảm bảo xử lý cả đồ thị không liên thông (mặc dù khái niệm khớp thường áp dụng cho đồ thị liên thông, thuật toán này vẫn tìm khớp trong từng thành phần liên thông).

Độ phức tạp của thuật toán này là O(V+E) vì mỗi đỉnh và mỗi cạnh đều được thăm đúng một lần trong quá trình DFS. Đây là một cải tiến đáng kể so với phương pháp ngây thơ.

Minh họa bằng Mã C++

Chúng ta sẽ cài đặt thuật toán tìm khớp dựa trên DFS sử dụng danh sách kề để biểu diễn đồ thị.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set> // Dùng set để lưu trữ khớp, tránh trùng lặp (nếu cạnh được thêm 2 chiều)

using namespace std;

const int MAXN = 1005; // Số đỉnh tối đa
vector<int> adj[MAXN]; // Danh sách kề
int disc[MAXN];        // Mảng lưu discovery time
int low[MAXN];         // Mảng lưu lowest reachable time
bool visited[MAXN];    // Mảng đánh dấu đã thăm
int timer;             // Bộ đếm thời gian cho DFS
set<pair<int, int>> bridges; // Tập hợp lưu trữ các khớp tìm được

// Hàm DFS chính để tìm khớp
// u: đỉnh hiện tại
// p: đỉnh cha của u trong cây DFS (-1 nếu u là gốc của cây DFS)
void findBridgesDFS(int u, int p = -1) {
    visited[u] = true;
    disc[u] = low[u] = timer++; // Gán discovery time và low time ban đầu

    // Duyệt qua tất cả các đỉnh kề của u
    for (int v : adj[u]) {
        // Nếu v là đỉnh cha, bỏ qua (để không coi cạnh quay về cha là cạnh ngược)
        if (v == p) continue;

        // Nếu v đã được thăm (là cạnh ngược)
        if (visited[v]) {
            // Cập nhật low[u]: ta có thể quay về đỉnh có disc[v] thông qua cạnh (u, v)
            low[u] = min(low[u], disc[v]);
        } 
        // Nếu v chưa được thăm (là cạnh cây)
        else {
            findBridgesDFS(v, u); // Đệ quy thăm v

            // Cập nhật low[u]: sau khi thăm cây con của v, low[u] có thể được cập nhật từ low[v]
            low[u] = min(low[u], low[v]);

            // Kiểm tra điều kiện khớp: nếu low[v] > disc[u], thì (u, v) là khớp
            // Điều này có nghĩa là không có cạnh ngược nào từ cây con của v
            // hoặc từ v đi ngược lên đỉnh u hoặc các tổ tiên của u.
            if (low[v] > disc[u]) {
                // Lưu cạnh (u, v) vào danh sách khớp
                // Luôn lưu theo thứ tự tăng dần để set loại bỏ trùng lặp (u,v) và (v,u)
                bridges.insert({min(u, v), max(u, v)});
            }
        }
    }
}

// Hàm chính để khởi tạo và gọi tìm khớp
void findBridges(int V) {
    // Khởi tạo các mảng
    timer = 0;
    bridges.clear();
    for (int i = 0; i < V; ++i) {
        visited[i] = false;
        disc[i] = -1; // Dùng -1 để dễ dàng kiểm tra chưa thăm
        low[i] = -1;
    }

    // Duyệt qua tất cả các đỉnh để đảm bảo xử lý cả đồ thị không liên thông
    // (Mặc dù khái niệm khớp thường xét trên đồ thị liên thông)
    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {
            findBridgesDFS(i);
        }
    }
}

// Hàm thêm cạnh vào đồ thị (đồ thị vô hướng)
void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int main() {
    // Ví dụ 1: Đồ thị đơn giản với một khớp
    // 0 -- 1 -- 2 -- 3 -- 4 -- 5
    //      |    |    |
    //      6 -- 7 -- 8
    // Cạnh (2, 3) là khớp

    int V1 = 9; // Số đỉnh
    // Reset danh sách kề cho ví dụ mới
    for(int i=0; i<V1; ++i) adj[i].clear(); 

    addEdge(0, 1);
    addEdge(1, 2);
    addEdge(2, 3); // Cạnh (2,3) là khớp tiềm năng
    addEdge(3, 4);
    addEdge(4, 5);
    addEdge(1, 6);
    addEdge(6, 7);
    addEdge(7, 2); // Cạnh (7,2) tạo chu trình (1,6,7,2)
    addEdge(7, 8); // Cạnh (7,8) tạo chu trình (2,3,4,...)? Không, (7,8) liên kết với chu trình (1,6,7,2)

    cout << "--- Vi du 1 ---" << endl;
    findBridges(V1);

    cout << "Cac khop trong do thi vi du 1:" << endl;
    if (bridges.empty()) {
        cout << "Khong co khop nao." << endl;
    } else {
        for (const auto& bridge : bridges) {
            cout << "(" << bridge.first << ", " << bridge.second << ")" << endl;
        }
    }
    cout << endl;

    // Ví dụ 2: Đồ thị phức tạp hơn
    // 0 -- 1 -- 2
    // |    |    |
    // 3 -- 4 -- 5
    // |         |
    // 6 -- 7 -- 8 -- 9
    // Khớp tiềm năng: (2,5), (5,8), (8,9)

    int V2 = 10; // Số đỉnh
    // Reset danh sách kề cho ví dụ mới
    for(int i=0; i<V2; ++i) adj[i].clear(); 

    addEdge(0, 1); addEdge(1, 2); addEdge(0, 3); addEdge(1, 4); addEdge(2, 5);
    addEdge(3, 4); addEdge(4, 5); addEdge(3, 6); addEdge(6, 7); addEdge(7, 8);
    addEdge(5, 8); // Cạnh (5,8) là khớp tiềm năng
    addEdge(8, 9); // Cạnh (8,9) là khớp tiềm năng

    cout << "--- Vi du 2 ---" << endl;
    findBridges(V2);

    cout << "Cac khop trong do thi vi du 2:" << endl;
    if (bridges.empty()) {
        cout << "Khong co khop nao." << endl;
    } else {
        for (const auto& bridge : bridges) {
            cout << "(" << bridge.first << ", " << bridge.second << ")" << endl;
        }
    }
    cout << endl;

    // Ví dụ 3: Đồ thị không có khớp (chỉ có chu trình)
    // 0 -- 1 -- 2
    // |    |    |
    // 3 -- 4 -- 5

    int V3 = 6; // Số đỉnh
    // Reset danh sách kề cho ví dụ mới
    for(int i=0; i<V3; ++i) adj[i].clear(); 

    addEdge(0, 1); addEdge(1, 2); addEdge(2, 5);
    addEdge(0, 3); addEdge(3, 4); addEdge(4, 1); // Tạo chu trình 0-1-4-3-0
    addEdge(4, 5); // Tạo chu trình 1-2-5-4-1 và 1-4-5-2-1

    cout << "--- Vi du 3 ---" << endl;
    findBridges(V3);

    cout << "Cac khop trong do thi vi du 3:" << endl;
    if (bridges.empty()) {
        cout << "Khong co khop nao." << endl;
    } else {
        for (const auto& bridge : bridges) {
            cout << "(" << bridge.first << ", " << bridge.second << ")" << endl;
        }
    }
    cout << endl;

    return 0;
}

Giải thích Mã C++

Đoạn mã trên cài đặt thuật toán tìm khớp dựa trên DFS như đã mô tả:

Biến toàn cục và mảng:
- MAXN: Giới hạn số đỉnh tối đa.
- adj: Mảng danh sách kề để biểu diễn đồ thị. adj[u] chứa danh sách các đỉnh kề với u.
- disc: Mảng disc[u] lưu thời gian khám phá đỉnh u. Ban đầu được khởi tạo là -1.
- low: Mảng low[u] lưu thời gian khám phá sớm nhất có thể đạt được từ đỉnh u hoặc cây con của nó thông qua một cạnh ngược. Ban đầu được khởi tạo là -1.
- visited: Mảng boolean đánh dấu xem đỉnh đã được thăm trong quá trình DFS chưa.
- timer: Biến đếm thời gian, tăng lên mỗi khi một đỉnh mới được khám phá.
- bridges: Một std::set<pair<int, int>> để lưu trữ các khớp tìm được. Sử dụng set với pair theo thứ tự tăng dần (min(u, v), max(u, v)) giúp tự động loại bỏ các cạnh trùng lặp (ví dụ (2,3) và (3,2)).
Hàm addEdge(u, v): Thêm một cạnh vô hướng giữa đỉnh u và v bằng cách thêm v vào danh sách kề của u và ngược lại.
Hàm findBridgesDFS(u, p):
- Đây là hàm DFS đệ quy. u là đỉnh hiện tại đang xét, p là đỉnh cha của u trong cây DFS (để phân biệt cạnh cây và cạnh ngược).
- Dòng visited[u] = true; disc[u] = low[u] = timer++;: Đánh dấu u đã thăm, gán thời gian khám phá và thời gian low ban đầu bằng timer hiện tại, sau đó tăng timer.
- Vòng lặp for (int v : adj[u]): Duyệt qua tất cả các đỉnh kề v của u.
- if (v == p) continue;: Nếu v là cha của u, bỏ qua vì cạnh (u, v) là cạnh cây đi ngược lên cha, không phải cạnh ngược thông thường.
- if (visited[v]): Nếu v đã thăm, đây là một cạnh ngược (u, v). Ta có thể đi từ u đến v (đã được thăm trước đó), nên cập nhật low[u] bằng min(low[u], disc[v]).
- else: Nếu v chưa thăm, đây là một cạnh cây (u, v).
  - findBridgesDFS(v, u);: Gọi đệ quy để thăm v (với u là cha của v).
  - low[u] = min(low[u], low[v]);: Sau khi đệ quy trả về, low[v] chứa thời gian sớm nhất có thể quay lại từ cây con của v. Cập nhật low[u] bằng cách lấy giá trị nhỏ nhất giữa low[u] hiện tại và low[v].
  - if (low[v] > disc[u]): Đây là điều kiện kiểm tra khớp. Nếu low[v] (thời gian sớm nhất có thể quay lại từ cây con của v) lớn hơn disc[u] (thời điểm u được khám phá), nghĩa là không có cách nào từ cây con của v quay ngược về u hoặc các tổ tiên của u mà không đi qua cạnh (u, v). Cạnh (u, v) là khớp.
  - bridges.insert({min(u, v), max(u, v)});: Thêm khớp vào set.
Hàm findBridges(V):
- Khởi tạo các mảng visited, disc, low và reset timer.
- Vòng lặp for (int i = 0; i < V; ++i): Đảm bảo rằng thuật toán bắt đầu DFS từ mọi đỉnh chưa được thăm. Điều này cần thiết nếu đồ thị ban đầu không liên thông. Mỗi lần DFS bắt đầu từ một đỉnh chưa thăm sẽ xử lý một thành phần liên thông mới.
Hàm main():
- Định nghĩa số đỉnh và cấu trúc đồ thị cho từng ví dụ.
- Gọi hàm findBridges() với số đỉnh tương ứng.
- In ra các khớp tìm được từ tập hợp bridges.

Lưu ý: Các chỉ số đỉnh trong code bắt đầu từ 0 đến V-1.

Phân tích các Ví dụ

Ví dụ 1: Đồ thị có dạng chu trình 1-6-7-2 và một "đuôi" 0-1 và một "đuôi" dài 2-3-4-5 nối với chu trình đó qua đỉnh 2. Cạnh (2,3) là điểm nối duy nhất giữa chuỗi 3-4-5 và phần còn lại của đồ thị. Bất kỳ đường đi nào từ 3 đến các đỉnh 0, 1, 6, 7, 2 đều phải đi qua cạnh (2,3). Do đó, (2,3) là khớp.
Ví dụ 2: Đồ thị này có hai chu trình lớn (0-1-4-3-0 và 1-2-5-4-1) được nối với nhau bởi các cạnh chung (1-4, 4-5, 1-2, 0-1, 0-3, 3-4, 2-5). Từ đỉnh 5, có một cạnh tới đỉnh 8. Từ đỉnh 8, có một cạnh tới đỉnh 9. Cạnh (5,8) là khớp vì nó là liên kết duy nhất giữa chu trình 0-1-2-5-4-3 và phần đồ thị 8-9. Tương tự, cạnh (8,9) là khớp vì nó là liên kết duy nhất giữa đỉnh 9 và phần còn lại của đồ thị.
Ví dụ 3: Đồ thị này là một lưới 2x3 (0-1-2, 3-4-5 và các cạnh dọc 0-3, 1-4, 2-5). Mọi cạnh trong đồ thị này đều nằm trong ít nhất một chu trình. Ví dụ, cạnh (1,2) nằm trong chu trình 1-2-5-4-1. Nếu xóa (1,2), ta vẫn có thể đi từ 1 đến 2 qua đường 1-4-5-2. Do đó, không có cạnh nào là khớp.

Bài tập ví dụ:

Xây dựng đường

Trong một chuyến đi khám phá thiên nhiên, FullHouse Dev đã đến thăm một vùng đất mới với nhiều thành phố nhưng chưa có đường giao thông. Họ được giao nhiệm vụ theo dõi quá trình xây dựng đường và phân tích sự kết nối giữa các thành phố.

Bài toán

Ban đầu có \(n\) thành phố và không có đường nối giữa chúng. Mỗi ngày, một con đường mới sẽ được xây dựng, và tổng cộng sẽ có \(m\) con đường. Một thành phần liên thông là một nhóm các thành phố mà từ thành phố này có thể đi đến bất kỳ thành phố nào khác trong nhóm bằng các con đường hiện có. Sau mỗi ngày, nhiệm vụ của bạn là tìm số lượng thành phần liên thông và kích thước của thành phần liên thông lớn nhất.

INPUT FORMAT:

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng thành phố và số lượng con đường. Các thành phố được đánh số từ \(1,2,\dots,n\).
\(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): một con đường mới được xây dựng giữa thành phố \(a\) và thành phố \(b\).
Mỗi con đường sẽ được xây dựng giữa hai thành phố khác nhau.

OUTPUT FORMAT:

In ra \(m\) dòng: thông tin yêu cầu sau mỗi ngày.

Ràng buộc:

\(1 \leq n \leq 10^5\)
\(1 \leq m \leq 2 \cdot 10^5\)
\(1 \leq a,b \leq n\)

Ví dụ

INPUT

OUTPUT

4 2
3 3
2 3

Giải thích

Sau ngày đầu tiên: có 4 thành phần liên thông (thành phố 1 và 2 kết nối với nhau, các thành phố 3, 4, và 5 riêng lẻ), và thành phần lớn nhất có kích thước 2.
Sau ngày thứ hai: có 3 thành phần liên thông (thành phố 1, 2, và 3 kết nối với nhau, thành phố 4 và 5 riêng lẻ), và thành phần lớn nhất có kích thước 3.
Sau ngày thứ ba: có 2 thành phần liên thông (thành phố 1, 2, và 3 kết nối với nhau, thành phố 4 và 5 kết nối với nhau), và thành phần lớn nhất có kích thước 3. Đây là hướng giải cho bài toán "Xây dựng đường" sử dụng cấu trúc dữ liệu Disjoint Set Union (DSU), còn gọi là Union-Find.

Ý tưởng chính:
- Bài toán yêu cầu theo dõi sự kết nối giữa các thành phố và thông tin về các thành phần liên thông sau mỗi khi một con đường mới được xây dựng.
- Cấu trúc dữ liệu DSU rất phù hợp cho việc quản lý các tập hợp không giao nhau (các thành phần liên thông ban đầu) và thực hiện thao tác hợp nhất (union) khi có đường nối giữa hai thành phố thuộc hai tập hợp khác nhau.
- DSU cho phép kiểm tra nhanh chóng hai phần tử có thuộc cùng một tập hợp hay không (find) và hợp nhất hai tập hợp (union).
Cấu trúc dữ liệu DSU:
- Sử dụng hai mảng chính:
  - parent[]: Mảng này lưu trữ "cha" của mỗi phần tử. Ban đầu, mỗi phần tử là "cha" của chính nó (parent[i] = i).
  - size[]: Mảng này lưu trữ kích thước của tập hợp mà phần tử đó là gốc (root). Ban đầu, mỗi tập hợp chỉ có 1 phần tử (size[i] = 1).
Các thao tác DSU cần thiết:
- find(i): Tìm phần tử đại diện (gốc - root) của tập hợp chứa phần tử i. Áp dụng kỹ thuật "nén đường" (path compression) để tối ưu hóa: trong quá trình tìm gốc, đặt trực tiếp "cha" của các phần tử trên đường đi về gốc.
- unite(a, b): Hợp nhất hai tập hợp chứa phần tử a và b.
  - Tìm gốc của a và b: root_a = find(a), root_b = find(b).
  - Nếu root_a == root_b, hai thành phố đã cùng thành phần liên thông. Không làm gì cả.
  - Nếu root_a != root_b, hai thành phố thuộc hai thành phần liên thông khác nhau. Hợp nhất hai tập hợp này. Áp dụng kỹ thuật "hợp nhất theo kích thước" (union by size): gán gốc của tập hợp nhỏ hơn làm con của gốc tập hợp lớn hơn. Cập nhật mảng parent và size cho gốc mới.
Theo dõi số thành phần liên thông và kích thước thành phần lớn nhất:
- Khởi tạo: Số thành phần liên thông ban đầu là n, kích thước thành phần lớn nhất ban đầu là 1.
- Khi thực hiện unite(a, b):
  - Nếu find(a) != find(b) (hai thành phần được hợp nhất):
    - Giảm số lượng thành phần liên thông đi 1.
    - Kích thước của thành phần mới là tổng kích thước của hai thành phần cũ.
    - Cập nhật kích thước thành phần lớn nhất nếu kích thước thành phần mới lớn hơn kích thước lớn nhất hiện tại.
  - Nếu find(a) == find(b), số lượng thành phần và kích thước lớn nhất không thay đổi.
Quy trình xử lý:
- Khởi tạo DSU cho n thành phố (mỗi thành phố là một tập hợp riêng).
- Khởi tạo biến đếm số thành phần liên thông (num_components = n) và kích thước thành phần lớn nhất (max_component_size = 1).
- Lặp lại m lần (mỗi lần đọc một con đường mới):
  - Đọc hai thành phố a và b của con đường mới.
  - Gọi thao tác unite(a, b). Thao tác này sẽ tự động xử lý việc hợp nhất, cập nhật parent, size, giảm num_components và cập nhật max_component_size nếu cần thiết (khi hai thành phần khác nhau được hợp nhất).
  - Sau khi xử lý con đường, in ra num_components và max_component_size hiện tại.
Lưu ý khi cài đặt:
- Các thành phố đánh số từ 1 đến n, nên các mảng parent và size cần có kích thước ít nhất là n+1.
- Sử dụng nhập/xuất nhanh (ví dụ: ios_base::sync_with_stdio(false); cin.tie(NULL); trong C++) để xử lý lượng dữ liệu lớn.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.