Bài 21.2. Thuật toán tìm cầu dựa trên DFS

Chào mừng trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Sau khi đã làm quen với những khái niệm cơ bản về đồ thị và các thuật toán duyệt như DFS (Depth First Search), hôm nay chúng ta sẽ cùng nhau dấn thân vào một lĩnh vực thú vị hơn: xác định các thành phần quan trọng của đồ thị. Cụ thể, chúng ta sẽ tìm hiểu về "cầu" (bridges) và cách sử dụng sức mạnh của DFS để tìm ra chúng.

"Cầu" Trong Đồ Thị Là Gì? Tại Sao Phải Tìm Chúng?

Hãy tưởng tượng đồ thị của chúng ta là một mạng lưới giao thông, một mạng máy tính, hoặc thậm chí là mối quan hệ giữa con người. Các đỉnh là các địa điểm/thiết bị/người, và các cạnh là các con đường/liên kết/mối quan hệ.

Một cạnh "cầu" (bridge) trong đồ thị vô hướng là một cạnh mà khi xóa bỏ nó, số lượng thành phần liên thông (connected components) của đồ thị tăng lên. Nói cách khác, nó là một liên kết sống còn, là điểm nghẽn (bottleneck) duy nhất nối hai phần của đồ thị.

Tại sao việc tìm cầu lại quan trọng?

Mạng lưới: Trong mạng lưới giao thông, cầu có thể là cây cầu bắc qua sông - điểm duy nhất kết nối hai bờ. Việc hư hỏng cây cầu này sẽ chia cắt giao thông. Trong mạng máy tính, nó có thể là một cáp mạng duy nhất nối hai phân mạng.
Độ tin cậy: Xác định cầu giúp đánh giá độ tin cậy của mạng lưới. Nếu có nhiều cầu, mạng đó kém bền vững hơn khi xảy ra lỗi đường truyền.
Phân tích: Trong các bài toán phân tích mạng xã hội hay sinh học, cầu có thể đại diện cho những mối quan hệ hoặc liên kết gen thiết yếu.

Việc tìm cầu bằng cách thử xóa từng cạnh và kiểm tra liên thông (ví dụ, bằng BFS hoặc DFS sau mỗi lần xóa) là cực kỳ kém hiệu quả. Với đồ thị có V đỉnh và E cạnh, cách làm "ngây thơ" này có độ phức tạp O(E * (V+E)), quá lớn cho đồ thị lớn.

May mắn thay, có một thuật toán thanh lịch và hiệu quả dựa trên DFS để giải quyết vấn đề này!

Sức Mạnh Của DFS: Thời Gian Khám Phá và "Điểm Thấp Nhất"

Thuật toán tìm cầu dựa trên DFS tận dụng hai khái niệm chính được thu thập trong quá trình duyệt:

Thời gian khám phá (Discovery Time - disc[u]): Đây là "dấu thời gian" khi đỉnh u lần đầu tiên được thăm trong quá trình DFS. Chúng ta có thể dùng một bộ đếm toàn cục (timer) tăng lên mỗi khi thăm một đỉnh mới. disc[u] sẽ là giá trị của timer tại thời điểm thăm u.
Thời gian đỉnh thấp nhất có thể tới (Lowest Reachable Ancestor Time - low[u]): Đây là giá trị disc nhỏ nhất có thể đạt được từ đỉnh u hoặc bất kỳ đỉnh nào trong cây con (subtree) của u trong cây DFS, bằng cách đi xuống các cạnh trong cây con và có thể đi ngược lên duy nhất một cạnh ngược (back edge) trở về một tổ tiên của u (hoặc chính u). Lưu ý quan trọng: Chúng ta không được sử dụng cạnh đi lên trực tiếp tới cha của u trong cây DFS để tính low[u].

Hãy cùng xem cách chúng ta tính toán disc và low trong quá trình DFS.

Khi duyệt DFS từ đỉnh u tới đỉnh v:

Bước 1: Khởi tạo: Khi bắt đầu thăm đỉnh u, gán disc[u] = low[u] = timer++. low[u] ban đầu được gán bằng disc[u] vì tệ nhất thì u chỉ có thể quay về chính nó.
Bước 2: Duyệt qua các đỉnh kề v của u:
- Nếu v là đỉnh cha của u trong cây DFS (đỉnh mà chúng ta vừa đi từ đó tới u), chúng ta bỏ qua cạnh này.
- Nếu v đã được thăm (visited): Điều này có nghĩa (u, v) là một cạnh ngược (back edge). Cạnh này cho phép chúng ta đi từ u (hoặc từ cây con của u thông qua u) quay ngược về đỉnh v vốn đã được thăm trước u. Vì v đã được thăm, v là tổ tiên của u hoặc nằm trong một phần đã thăm khác. low[u] có thể được cập nhật thành min(low[u], disc[v]).
- Nếu v chưa được thăm: (u, v) là một cạnh cây (tree edge). Chúng ta đệ quy gọi DFS cho v (với u là cha của v). Sau khi lời gọi đệ quy DFS(v, u) kết thúc, chúng ta đã tính được low[v]. low[u] có thể được cập nhật thành min(low[u], low[v]). Điều này có nghĩa là u có thể "kế thừa" khả năng quay về điểm có disc thấp nhất mà v hoặc cây con của v có thể tới được.

Điều Kiện Phát Hiện Cầu

Bây giờ, phần ma thuật nằm ở đây. Sau khi gọi đệ quy DFS(v, u) và tính toán xong low[v], chúng ta kiểm tra điều kiện:

Nếu low[v] > disc[u], thì cạnh (u, v) là một cầu!

Giải thích: Điều kiện low[v] > disc[u] có nghĩa là điểm có disc thấp nhất mà đỉnh v hoặc bất kỳ đỉnh nào trong cây con của v có thể đạt được (bằng cách đi xuống trong cây con và sử dụng tối đa một cạnh ngược) vẫn có thời gian khám phá lớn hơn thời gian khám phá của u. Điều này chỉ xảy ra khi không có bất kỳ cạnh ngược nào từ cây con của v (bao gồm cả v) quay trở lại u hoặc bất kỳ tổ tiên nào của u. Do đó, cạnh (u, v) là con đường duy nhất để kết nối cây con của v với phần còn lại của đồ thị (bao gồm u và các tổ tiên của u). Khi xóa (u, v), cây con của v sẽ bị ngắt kết nối.

Thuật Toán Chi Tiết

Khởi tạo:
- Một danh sách kề (adj) để biểu diễn đồ thị.
- Mảng visited (hoặc bool visited[]) để đánh dấu đỉnh đã thăm.
- Mảng disc[] để lưu thời gian khám phá.
- Mảng low[] để lưu thời gian đỉnh thấp nhất có thể tới.
- Một bộ đếm thời gian toàn cục timer = 0.
- Một danh sách để lưu trữ các cạnh cầu tìm được.
Lặp qua tất cả các đỉnh u từ 0 đến V-1. Nếu u chưa được thăm, gọi hàm DFS tìm cầu bắt đầu từ u: bridgeDFS(u, -1). (Truyền -1 làm cha của đỉnh bắt đầu để đánh dấu nó không có cha).
Hàm bridgeDFS(u, parent):
- Đánh dấu u đã thăm: visited[u] = true.
- Gán thời gian khám phá và low ban đầu cho u: disc[u] = low[u] = timer++.
- Với mỗi đỉnh kề v của u:
  - Nếu v == parent, bỏ qua (không đi ngược lên cạnh vừa tới).
  - Nếu v đã thăm: low[u] = min(low[u], disc[v]). Đây là cạnh ngược.
  - Nếu v chưa thăm:
    - Gọi đệ quy: bridgeDFS(v, u).
    - Sau khi đệ quy kết thúc, cập nhật low[u] = min(low[u], low[v]).
    - KIỂM TRA CẦU: Nếu low[v] > disc[u], thì cạnh (u, v) là một cầu. Lưu lại cặp (u, v) hoặc (v, u).

Ví Dụ Minh Họa 1: Đồ Thị Đơn Giản

Xét đồ thị có 5 đỉnh (0, 1, 2, 3, 4) và các cạnh: (0,1), (0,2), (1,2), (2,3), (3,4).

Đồ thị trông như sau (mô tả): 0 -- 1 | \ | 2 -- 3 -- 4

Các cạnh (0,1), (0,2), (1,2) tạo thành một tam giác. Cạnh (2,3) nối tam giác này với đỉnh 3. Cạnh (3,4) nối 3 với 4. Rõ ràng, xóa (2,3) sẽ tách {0,1,2} khỏi {3,4}. Xóa (3,4) sẽ tách 4 khỏi {0,1,2,3}. Chúng ta kỳ vọng tìm thấy hai cầu: (2,3) và (3,4).

Hãy chạy DFS bắt đầu từ đỉnh 0.

timer = 0
Gọi bridgeDFS(0, -1):
- visited[0] = true, disc[0] = low[0] = 0, timer = 1.
- Xét kề của 0:
  - Đỉnh 1: Chưa thăm. Gọi bridgeDFS(1, 0):
    - visited[1] = true, disc[1] = low[1] = 1, timer = 2.
    - Xét kề của 1:
      - Đỉnh 0: Là cha (parent). Bỏ qua.
      - Đỉnh 2: Chưa thăm. Gọi bridgeDFS(2, 1):
        
        visited[2] = true, disc[2] = low[2] = 2, timer = 3.
        
        Xét kề của 2:
        
        Đỉnh 0: Đã thăm. Cạnh ngược (2,0). disc[0] = 0. low[2] = min(low[2], disc[0]) = min(2, 0) = 0. Đỉnh 1: Là cha. Bỏ qua. Đỉnh 3: Chưa thăm. Gọi bridgeDFS(3, 2): visited[3] = true, disc[3] = low[3] = 3, timer = 4. Xét kề của 3: Đỉnh 2: Là cha. Bỏ qua. Đỉnh 4: Chưa thăm. Gọi bridgeDFS(4, 3): visited[4] = true, disc[4] = low[4] = 4, timer = 5. Xét kề của 4: Đỉnh 3: Là cha. Bỏ qua. Hết kề của 4. Đệ quy DFS(4,3) kết thúc. low[4] vẫn là 4. Trở về DFS(3,2). Đệ quy từ 4 kết thúc. Cập nhật low[3] = min(low[3], low[4]) = min(3, 4) = 3. KIỂM TRA CẦU (3,4): low[4] = 4, disc[3] = 3. 4 > 3 -> (3,4) là cầu! Lưu lại. Hết kề của 3. Đệ quy DFS(3,2) kết thúc. low[3] vẫn là 3. Trở về DFS(2,1). Đệ quy từ 3 kết thúc. Cập nhật low[2] = min(low[2], low[3]) = min(0, 3) = 0. KIỂM TRA CẦU (2,3): low[3] = 3, disc[2] = 2. 3 > 2 -> (2,3) là cầu! Lưu lại.
        
        Hết kề của 2. Đệ quy DFS(2,1) kết thúc.
        
        low[2] vẫn là 0.
      - Trở về DFS(1,0). Đệ quy từ 2 kết thúc.
      - Cập nhật low[1] = min(low[1], low[2]) = min(1, 0) = 0.
      - KIỂM TRA CẦU (1,2): low[2] = 0, disc[1] = 1. 0 > 1 là sai. (1,2) không phải cầu.
    - Hết kề của 1. Đệ quy DFS(1,0) kết thúc.
    - low[1] vẫn là 0.
  - Trở về DFS(0,-1). Đệ quy từ 1 kết thúc.
  - Cập nhật low[0] = min(low[0], low[1]) = min(0, 0) = 0.
  - KIỂM TRA CẦU (0,1): low[1] = 0, disc[0] = 0. 0 > 0 là sai. (0,1) không phải cầu.
  - Đỉnh 2: Đã thăm. Cạnh (0,2). v=2 đã thăm. disc[2] = 2.
  - Cập nhật low[0] = min(low[0], disc[2]) = min(0, 2) = 0. (Cạnh ngược (0,2) cho phép 0 quay về đỉnh 2 có disc=2, nhưng 0 đã có thể quay về đỉnh có disc=0 thông qua 1 và cạnh ngược (1,2)).
- Hết kề của 0. Đệ quy DFS(0,-1) kết thúc. low[0] vẫn là 0.
Kiểm tra các đỉnh khác (1, 2, 3, 4). Tất cả đều đã thăm.

Quá trình DFS kết thúc. Chúng ta đã tìm thấy hai cầu: (3,4) và (2,3). Chính xác như dự đoán!

Các giá trị disc và low cuối cùng: disc: {0:0, 1:1, 2:2, 3:3, 4:4} low: {0:0, 1:0, 2:0, 3:3, 4:4}

Kiểm tra cầu theo cây DFS (cha -> con): (0,1): low[1] (0) <= disc[0] (0). Không phải cầu. (0,2): (0,2) là cạnh ngược, không phải cạnh cây đi xuống từ 0. (1,2): low[2] (0) <= disc[1] (1). Không phải cầu. (2,3): low[3] (3) > disc[2] (2). Là cầu. (3,4): low[4] (4) > disc[3] (3). Là cầu.

Cài Đặt Bằng C++

Đây là đoạn code C++ minh họa thuật toán tìm cầu dựa trên DFS:

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

// Sử dụng namespace std cho tiện lợi
using namespace std;

// Cấu trúc để lưu trữ đồ thị
vector<vector<int>> adj;
// Mảng đánh dấu đỉnh đã thăm
vector<bool> visited;
// Mảng lưu thời gian khám phá (discovery time)
vector<int> disc;
// Mảng lưu thời gian đỉnh thấp nhất có thể tới (lowest reachable ancestor time)
vector<int> low;
// Bộ đếm thời gian toàn cục
int timer;
// Danh sách lưu trữ các cạnh cầu tìm được
vector<pair<int, int>> bridges;

// Hàm DFS để tìm cầu
// u: đỉnh hiện tại
// parent: đỉnh cha của u trong cây DFS
void findBridgesDFS(int u, int parent = -1) {
    // Đánh dấu u đã thăm và gán thời gian khám phá/low ban đầu
    visited[u] = true;
    disc[u] = low[u] = timer++;

    // Duyệt qua tất cả các đỉnh kề v của u
    for (int v : adj[u]) {
        // Nếu v là đỉnh cha, bỏ qua
        if (v == parent) {
            continue;
        }

        // Nếu v đã được thăm
        if (visited[v]) {
            // v đã thăm và không phải là cha -> (u,v) là cạnh ngược
            // Cập nhật low[u]
            low[u] = min(low[u], disc[v]);
        } else {
            // v chưa được thăm -> (u,v) là cạnh cây
            // Gọi đệ quy cho v
            findBridgesDFS(v, u);

            // Sau khi đệ quy cho v kết thúc, cập nhật low[u]
            // low[u] có thể đạt được giá trị low[v] (thông qua cạnh cây (u,v))
            low[u] = min(low[u], low[v]);

            // KIỂM TRA CẦU: Nếu low[v] > disc[u]
            // Điều này có nghĩa là không có đường nào từ v (hoặc cây con của v)
            // đi ngược lên u hoặc tổ tiên của u ngoại trừ cạnh (u,v)
            if (low[v] > disc[u]) {
                bridges.push_back({u, v});
            }
        }
    }
}

// Hàm chính để tìm tất cả các cầu trong đồ thị
void findBridges(int n) {
    // Khởi tạo lại các mảng và biến cho mỗi lần tìm kiếm trên đồ thị mới
    visited.assign(n, false);
    disc.assign(n, -1); // -1 để đánh dấu chưa khám phá
    low.assign(n, -1);
    timer = 0;
    bridges.clear();

    // Lặp qua tất cả các đỉnh để đảm bảo xử lý cả đồ thị không liên thông
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            findBridgesDFS(i); // Bắt đầu DFS từ đỉnh chưa thăm
        }
    }

    // In kết quả
    cout << "Cac canh cau (bridges) trong do thi:" << endl;
    for (const auto& bridge : bridges) {
        cout << bridge.first << " -- " << bridge.second << endl;
    }
}

int main() {
    // Ví dụ 1: Đồ thị đơn giản (từ minh họa trên)
    int n1 = 5; // Số đỉnh
    adj.assign(n1, vector<int>()); // Xóa đồ thị cũ và tạo mới

    // Thêm cạnh
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(2); adj[2].push_back(1);
    adj[2].push_back(3); adj[3].push_back(2);
    adj[3].push_back(4); adj[4].push_back(3);

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

    cout << endl;

    // Ví dụ 2: Đồ thị phức tạp hơn một chút
    // 0 -- 1 -- 2
    // |    |    |
    // 3 -- 4 -- 5 -- 6
    //      \   /
    //       \ /
    //        7
    int n2 = 8;
    adj.assign(n2, vector<int>());

    adj[0].push_back(1); adj[1].push_back(0);
    adj[1].push_back(2); adj[2].push_back(1);
    adj[1].push_back(4); adj[4].push_back(1); // Cạnh (1,4)
    adj[0].push_back(3); adj[3].push_back(0); // Cạnh (0,3)
    adj[3].push_back(4); adj[4].push_back(3); // Cạnh (3,4)
    adj[2].push_back(5); adj[5].push_back(2); // Cạnh (2,5)
    adj[4].push_back(5); adj[5].push_back(4); // Cạnh (4,5)
    adj[5].push_back(6); adj[6].push_back(5); // Cạnh (5,6) - KỲ VỌNG LÀ CẦU
    adj[4].push_back(7); adj[7].push_back(4); // Cạnh (4,7)
    adj[5].push_back(7); adj[7].push_back(5); // Cạnh (5,7)

    cout << "--- Vi du 2 ---" << endl;
    findBridges(n2);
    // Kỳ vọng: (5,6) là cầu duy nhất. Các cạnh khác nằm trong các chu trình.

    return 0;
}

Giải Thích Code C++

#include và using namespace std;: Bao gồm các thư viện cần thiết và sử dụng namespace chuẩn C++.
Biến Toàn Cục/Class Members:
- vector<vector<int>> adj: Biểu diễn đồ thị bằng danh sách kề. adj[i] là vector chứa các đỉnh kề với đỉnh i.
- vector<bool> visited: Mảng boolean để theo dõi đỉnh nào đã được thăm trong quá trình DFS.
- vector<int> disc: Mảng lưu thời gian khám phá cho mỗi đỉnh. Khởi tạo bằng -1 để dễ kiểm tra.
- vector<int> low: Mảng lưu giá trị low cho mỗi đỉnh. Khởi tạo bằng -1.
- int timer: Bộ đếm thời gian, tăng lên mỗi khi một đỉnh mới được gán disc.
- vector<pair<int, int>> bridges: Danh sách để lưu trữ các cạnh cầu được tìm thấy. pair<int, int> lưu cặp đỉnh của cạnh.
findBridgesDFS(int u, int parent) Function:
- Đây là hàm đệ quy thực hiện DFS và tính toán disc, low, cũng như kiểm tra cầu.
- parent = -1: Tham số mặc định này giúp xử lý đỉnh gốc của mỗi cây DFS (trong trường hợp đồ thị không liên thông), đảm bảo nó không cố gắng đi ngược lên "cha" không tồn tại.
- visited[u] = true; disc[u] = low[u] = timer++;: Bước khởi tạo khi thăm đỉnh u. Gán thời gian khám phá và low ban đầu, sau đó tăng bộ đếm thời gian.
- for (int v : adj[u]): Lặp qua tất cả các đỉnh v kề với u.
- if (v == parent) continue;: Bỏ qua cạnh nối với cha để tránh đi ngược lên cây DFS một cách "bình thường".
- if (visited[v]): Nếu đỉnh kề v đã thăm: Đây là trường hợp cạnh ngược. Chúng ta cập nhật low[u] bằng giá trị nhỏ nhất giữa low[u] hiện tại và disc[v]. Điều này thể hiện rằng từ u, chúng ta có thể đi qua cạnh ngược (u, v) và đạt tới một đỉnh v có thời gian khám phá disc[v].
- else: Nếu đỉnh kề v chưa thăm: Đây là trường hợp cạnh cây.
  - findBridgesDFS(v, u);: Gọi đệ quy cho đỉnh v, đặt u làm cha của v.
  - low[u] = min(low[u], low[v]);: Sau khi lời gọi đệ quy kết thúc, low[v] đã được tính toán. Ta cập nhật low[u]. Nếu v hoặc cây con của v có thể tới một đỉnh có disc thấp hơn low[u] hiện tại (thông qua các cạnh cây hoặc cạnh ngược trong cây con của v), thì u cũng có thể tới điểm đó thông qua cạnh (u,v).
  - if (low[v] > disc[u]): Kiểm tra cầu. Nếu low[v] vẫn lớn hơn disc[u], điều đó khẳng định không có cạnh ngược nào từ cây con của v đi lên tới u hoặc các tổ tiên của u. Cạnh (u, v) là cầu. Thêm vào danh sách bridges.
findBridges(int n) Function:
- Hàm này là điểm bắt đầu. Nó nhận số lượng đỉnh n.
- Nó khởi tạo lại các mảng và biến toàn cục.
- Nó lặp qua tất cả các đỉnh từ 0 đến n-1. Nếu một đỉnh chưa được thăm (!visited[i]), điều đó có nghĩa nó thuộc về một thành phần liên thông mới (hoặc là đỉnh đầu tiên trong đồ thị), và ta bắt đầu quá trình DFS tìm cầu từ đó bằng cách gọi findBridgesDFS(i).
- Cuối cùng, nó in ra danh sách các cầu tìm được.
main() Function:
- Thiết lập các ví dụ đồ thị khác nhau.
- Đối với mỗi ví dụ:
  - Thiết lập số lượng đỉnh n.
  - Xóa và cấu hình lại danh sách kề adj.
  - Thêm các cặp cạnh vào danh sách kề (lưu ý: vì là đồ thị vô hướng, cần thêm cạnh cả hai chiều, ví dụ adj[u].push_back(v); adj[v].push_back(u);).
  - Gọi findBridges(n) để chạy thuật toán và in kết quả.

Ví Dụ Minh Họa 2: Đồ Thị Phức Tạp Hơn

Xét đồ thị thứ hai trong code:

0 -- 1 -- 2
|    |    |
3 -- 4 -- 5 -- 6
     \   /
      \ /
       7

Chúng ta có hai chu trình: {0,1,4,3} và {1,2,5,4} và {4,5,7}. Cạnh (5,6) là cạnh duy nhất đi ra khỏi cụm các chu trình này. Kỳ vọng: Cạnh (5,6) là cầu.

Chạy code C++ sẽ cho ra kết quả:

--- Vi du 1 ---
Cac canh cau (bridges) trong do thi:
3 -- 4
2 -- 3

--- Vi du 2 ---
Cac canh cau (bridges) trong do thi:
5 -- 6

Kết quả này chính xác với phân tích của chúng ta.

Độ Phức Tạp

Thuật toán này dựa trên DFS. Mỗi đỉnh và mỗi cạnh được thăm đúng một lần. Do đó, độ phức tạp thời gian là O(V + E), trong đó V là số đỉnh và E là số cạnh. Độ phức tạp không gian là O(V + E) để lưu trữ đồ thị (danh sách kề) và các mảng visited, disc, low, và danh sách cầu (kích thước tối đa O(E)).

Đây là một cải tiến đáng kể so với phương pháp thử xóa từng cạnh.

Bài tập ví dụ:

Sửa Chữa Đường

Trong một buổi họp quản lý, FullHouse Dev được giao nhiệm vụ tối ưu hóa chi phí vận chuyển hàng hóa giữa các siêu thị. Họ nhận thấy rằng các tuyến đường kết nối giữa các siêu thị đang trong tình trạng xuống cấp và cần được sửa chữa. Trên tinh thần tiết kiệm chi phí, FullHouse Dev bắt đầu lên kế hoạch sửa chữa đường sao cho tổng chi phí là thấp nhất.

Bài toán

Có \(n\) siêu thị và \(m\) con đường nối giữa chúng. Tất cả các con đường đều đang trong tình trạng không thể sử dụng được. Nhiệm vụ của bạn là sửa chữa một số con đường sao cho có thể di chuyển giữa bất kỳ hai siêu thị nào, với tổng chi phí sửa chữa là thấp nhất có thể.

INPUT FORMAT:

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng siêu thị và số lượng con đường. Các siêu thị được đánh số từ \(1\) đến \(n\).
\(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(c\): có một con đường nối giữa siêu thị \(a\) và siêu thị \(b\), với chi phí sửa chữa là \(c\). Tất cả các con đường đều là đường hai chiều.
Mỗi con đường nối giữa hai siêu thị khác nhau và giữa hai siêu thị chỉ có tối đa một con đường.

OUTPUT FORMAT:

In ra một số nguyên: tổng chi phí sửa chữa tối thiểu. Nếu không có giải pháp, in ra "IMPOSSIBLE".

Ràng buộc:

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

Ví dụ

INPUT

OUTPUT

Giải thích

Trong ví dụ này, FullHouse Dev có thể chọn sửa chữa các con đường sau:

Đường từ siêu thị 1 đến siêu thị 2 (chi phí 3)
Đường từ siêu thị 2 đến siêu thị 4 (chi phí 2)
Đường từ siêu thị 2 đến siêu thị 3 (chi phí 5)
Đường từ siêu thị 4 đến siêu thị 5 (chi phí 4) Tổng chi phí sửa chữa là 14, và với những con đường này, có thể di chuyển giữa bất kỳ hai siêu thị nào. Đây là bài toán tìm Cây Bao Trùm Nhỏ Nhất (Minimum Spanning Tree - MST).

Hướng giải ngắn gọn:

Xác định bài toán: Bài toán yêu cầu tìm tập hợp các cạnh (đường) có tổng trọng số (chi phí) nhỏ nhất sao cho tất cả các đỉnh (siêu thị) được nối lại với nhau (tạo thành một thành phần liên thông). Đây chính xác là định nghĩa của Cây Bao Trùm Nhỏ Nhất.
Chọn thuật toán: Sử dụng thuật toán Kruskal. Thuật toán này hoạt động tốt với các đồ thị thưa (số cạnh m không quá lớn so với n^2) và khá dễ cài đặt kết hợp với DSU.
Các bước thực hiện thuật toán Kruskal:
- Lưu trữ tất cả các cạnh cùng với chi phí của chúng.
- Sắp xếp các cạnh theo thứ tự chi phí tăng dần.
- Khởi tạo một cấu trúc dữ liệu Disjoint Set Union (DSU) cho n siêu thị. Ban đầu, mỗi siêu thị là một tập hợp riêng biệt.
- Khởi tạo tổng chi phí sửa chữa bằng 0 và đếm số cạnh đã chọn bằng 0.
- Duyệt qua các cạnh đã sắp xếp:
  - Với mỗi cạnh nối hai siêu thị a và b với chi phí c:
  - Kiểm tra xem a và b có đang ở trong cùng một thành phần liên thông hay không bằng cách sử dụng thao tác find của DSU.
  - Nếu a và b ở khác thành phần:
    - Thêm cạnh này vào MST.
    - Cộng chi phí c vào tổng chi phí.
    - Gộp hai thành phần của a và b lại với nhau bằng thao tác union của DSU.
    - Tăng số cạnh đã chọn lên 1.
Kiểm tra điều kiện "IMPOSSIBLE":
- MST tồn tại khi và chỉ khi đồ thị gốc là liên thông.
- Trong thuật toán Kruskal, nếu đồ thị liên thông, ta sẽ chọn được đúng n-1 cạnh để nối tất cả n đỉnh thành một cây duy nhất (nếu n > 1).
- Sau khi duyệt hết tất cả m cạnh, kiểm tra xem ta đã chọn được bao nhiêu cạnh. Nếu số cạnh đã chọn nhỏ hơn n-1 (với n > 1), điều đó có nghĩa là không thể nối tất cả các siêu thị lại với nhau, in ra "IMPOSSIBLE". (Trường hợp n=1 thì chi phí là 0, luôn có giải pháp).
- Nếu số cạnh đã chọn là n-1 (với n > 1), thì ta đã tìm được MST và tổng chi phí là kết quả cần in.
Cấu trúc dữ liệu cần dùng: Disjoint Set Union (DSU) để quản lý và thao tác trên các thành phần liên thông một cách hiệu quả (kiểm tra thuộc cùng thành phần và gộp hai thành phầ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.