Bài 23.3. Ứng dụng Tarjan trong tìm khớp

Trong thế giới rộng lớn của lý thuyết đồ thị, việc hiểu rõ cấu trúc và sự kết nối của đồ thị là vô cùng quan trọng. Một trong những vấn đề cơ bản và thiết thực là xác định các "điểm yếu" trong mạng lưới kết nối - những điểm mà nếu bị loại bỏ sẽ phá vỡ sự liên thông của đồ thị. Đó chính là khái niệm về đỉnh khớp (Articulation Point), còn được gọi là đỉnh cắt (Cut Vertex).

Trong bài viết này, chúng ta sẽ đào sâu vào việc tìm kiếm các đỉnh khớp này bằng một giải thuật kinh điển và hiệu quả: Thuật toán Tarjan.

Đỉnh khớp (Articulation Point) là gì?

Một đỉnh khớp trong một đồ thị vô hướng liên thông là một đỉnh mà việc loại bỏ nó (cùng với tất cả các cạnh liên thuộc với nó) sẽ làm tăng số thành phần liên thông của đồ thị.

Nói cách khác, nếu đồ thị ban đầu là liên thông, việc loại bỏ một đỉnh khớp sẽ làm đồ thị trở thành không liên thông. Nếu đồ thị ban đầu đã không liên thông, việc loại bỏ một đỉnh khớp sẽ tạo ra thêm một hoặc nhiều thành phần liên thông mới.

Hãy hình dung một mạng lưới đường bộ. Một thành phố là đỉnh khớp nếu việc đóng cửa thành phố đó khiến một số khu vực không thể đi đến được từ những khu vực khác. Trong mạng máy tính, một máy chủ là đỉnh khớp nếu việc nó ngừng hoạt động khiến mạng bị chia cắt.

Việc tìm ra các đỉnh khớp có ứng dụng thực tế trong nhiều lĩnh vực:

Thiết kế mạng: Xác định các điểm yếu tiềm tàng trong mạng lưới giao thông, mạng máy tính, mạng lưới điện...
Độ tin cậy của hệ thống: Tìm ra các thành phần quan trọng mà sự cố của chúng có thể gây ra hậu quả lớn.
Phân tích mạng xã hội: Tìm ra những cá nhân đóng vai trò cầu nối quan trọng giữa các nhóm.

Làm sao để tìm các đỉnh khớp một cách hiệu quả? Cách đơn giản nhất là thử loại bỏ từng đỉnh một và kiểm tra xem đồ thị có còn liên thông hay không (ví dụ, bằng BFS hoặc DFS). Tuy nhiên, với đồ thị có V đỉnh và E cạnh, việc kiểm tra liên thông mất O(V+E). Lặp lại cho mỗi đỉnh sẽ mất O(V * (V+E)), quá chậm với đồ thị lớn.

May mắn thay, thuật toán Tarjan cho phép chúng ta tìm tất cả các đỉnh khớp chỉ trong một lần duyệt đồ thị (DFS).

Sức mạnh của Tarjan: Duyệt đồ thị và Theo dõi "Độ liên thông ngược"

Thuật toán Tarjan dựa trên Duyệt theo chiều sâu (DFS) và sử dụng hai giá trị quan trọng được tính toán cho mỗi đỉnh u:

disc[u] (Discovery Time): Thời điểm (thứ tự bước) mà đỉnh u được thăm lần đầu tiên trong quá trình DFS. Chúng ta có thể sử dụng một bộ đếm toàn cục (timer) tăng dần mỗi khi thăm một đỉnh mới.
low[u] (Low-Link Value): Thời điểm khám phá sớm nhất (disc nhỏ nhất) mà đỉnh u hoặc bất kỳ đỉnh nào trong cây con DFS của u có thể kết nối tới thông qua ít nhất một cạnh ngược (back-edge) và nhiều nhất một cạnh ngược. Về cơ bản, low[u] cho biết đỉnh có disc nhỏ nhất mà ta có thể "quay trở lại" từ u hoặc từ cây con của u.

Mối liên hệ giữa disc[u] và low[u] chính là chìa khóa để xác định đỉnh khớp và cả cạnh cầu (bridge).

Cơ chế xác định Đỉnh khớp trong Tarjan

Khi duyệt DFS từ đỉnh u sang đỉnh v (giả sử v là con của u trong cây DFS), chúng ta gọi đệ quy DFS(v, u). Sau khi lời gọi đệ quy DFS(v, u) kết thúc, chúng ta cập nhật low[u] dựa trên low[v]: low[u] = min(low[u], low[v]). Điều này đảm bảo rằng low[u] phản ánh thời điểm sớm nhất có thể đạt được từ toàn bộ cây con của u (bao gồm cả cây con của v).

Ngoài ra, nếu v đã được thăm và không phải là cha trực tiếp của u (v != parent), thì cạnh (u, v) là một cạnh ngược. Cạnh ngược này cho phép ta đi từ u đến v (đã thăm), và disc[v] là thời điểm khám phá của v. Ta có thể cập nhật low[u] bằng cách lấy min(low[u], disc[v]), vì từ u ta có thể đi qua cạnh ngược này để đạt tới v (với thời điểm khám phá disc[v]).

Bây giờ, hãy xem điều kiện để một đỉnh u là đỉnh khớp:

Trường hợp u là gốc (root) của cây DFS: u là gốc nếu nó được gọi đầu tiên trong một lần DFS (ví dụ: parent == -1). u là đỉnh khớp nếu và chỉ nếu nó có ít nhất hai con trong cây DFS. Nếu nó chỉ có một con, việc loại bỏ gốc chỉ tách riêng cây con đó ra, nhưng gốc vẫn liên thông với phần còn lại của đồ thị (nếu có), hoặc đồ thị chỉ còn cây con đó (nếu nó là thành phần liên thông duy nhất). Nếu có hai con trở lên, việc loại bỏ gốc sẽ ngắt kết nối giữa các cây con này.
Trường hợp u không phải là gốc (root): u là đỉnh khớp nếu tồn tại một đỉnh con v của u trong cây DFS sao cho low[v] >= disc[u].
- Điều kiện low[v] >= disc[u] nghĩa là gì? Nó có nghĩa là không có cách nào để đi từ đỉnh v hoặc bất kỳ đỉnh nào trong cây con của v đến một đỉnh có thời gian khám phá nghiêm ngặt nhỏ hơn disc[u] mà không đi qua đỉnh u. Tất cả các đường đi "ngược" từ cây con của v đều chỉ có thể lên đến u (hoặc cao hơn u, nhưng điều đó không giúp ích gì trong việc kết nối v ra khỏi u nếu u bị xóa).
- Do đó, nếu low[v] >= disc[u], việc loại bỏ đỉnh u sẽ làm ngắt kết nối giữa đỉnh v (và toàn bộ cây con của nó) với phần còn lại của đồ thị (hoặc ít nhất là phần của đồ thị có disc nhỏ hơn disc[u]). Đỉnh u trở thành một "nút thắt cổ chai".

Lưu ý: Khi kiểm tra điều kiện low[v] >= disc[u] cho trường hợp không phải gốc, chúng ta cần đảm bảo đỉnh u không phải là gốc của toàn bộ cây DFS mà đang xét.

Cài đặt thuật toán Tarjan bằng C++

Để cài đặt, chúng ta cần:

Danh sách kề (adj) để biểu diễn đồ thị.
Các mảng disc, low có kích thước bằng số đỉnh, khởi tạo với giá trị đặc biệt (ví dụ: -1) để đánh dấu chưa thăm.
Mảng visited kiểu boolean hoặc dùng giá trị trong disc (-1 vs >=0).
Một biến timer toàn cục, khởi tạo bằng 0.
Một cấu trúc dữ liệu (ví dụ: std::set hoặc std::vector) để lưu trữ các đỉnh khớp tìm được. set tự động xử lý các trường hợp đỉnh khớp được thêm vào nhiều lần.
Hàm DFS đệ quy DFS(u, parent).

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

const int MAXN = 10005; // Số đỉnh tối đa, điều chỉnh nếu cần

vector<vector<int>> adj;
vector<int> disc, low;
vector<bool> visited;
int timer;
set<int> articulation_points; // Sử dụng set để lưu trữ và loại bỏ trùng lặp

// Hàm DFS chính để tìm đỉnh khớp
void find_articulation_points_dfs(int u, int parent = -1) {
    visited[u] = true;
    disc[u] = low[u] = timer++; // Gán thời gian khám phá và low-link ban đầu
    int children_count = 0; // Đếm số con trong cây DFS cho trường hợp gốc

    // Duyệt qua tất cả các đỉnh kề của u
    for (int v : adj[u]) {
        // Bỏ qua cạnh nối về cha trong cây DFS
        if (v == parent) continue;

        // Nếu v đã được thăm -> cạnh (u, v) là cạnh ngược
        if (visited[v]) {
            // Cập nhật low[u]: ta có thể đi từ u đến v (đã thăm)
            low[u] = min(low[u], disc[v]);
        }
        // Nếu v chưa được thăm -> cạnh (u, v) là cạnh cây
        else {
            children_count++; // Tăng số con trong cây DFS
            find_articulation_points_dfs(v, u); // Duyệt đệ quy v với u là cha

            // Sau khi gọi đệ quy xong, cập nhật low[u]
            // low[u] có thể kết nối tới thời điểm sớm nhất mà v hoặc cây con của v kết nối tới
            low[u] = min(low[u], low[v]);

            // Kiểm tra điều kiện đỉnh khớp

            // Trường hợp 1: u là gốc của cây DFS (parent == -1)
            // u là đỉnh khớp nếu có ít nhất 2 con trong cây DFS
            if (parent == -1 && children_count > 1) {
                articulation_points.insert(u);
            }
            // Trường hợp 2: u không phải là gốc
            // u là đỉnh khớp nếu low[v] >= disc[u].
            // Điều này có nghĩa là cây con tại v KHÔNG có cạnh ngược nào kết nối VÀO
            // một đỉnh có disc nhỏ hơn disc[u]. Do đó, loại bỏ u sẽ ngắt kết nối
            // cây con tại v với phần còn lại của đồ thị "phía trên" u.
            if (parent != -1 && low[v] >= disc[u]) {
                articulation_points.insert(u);
            }
        }
    }
}

// Hàm bao bọc để xử lý đồ thị có thể không liên thông
void find_articulation_points(int n) {
    disc.assign(n, -1);
    low.assign(n, -1);
    visited.assign(n, false);
    timer = 0;
    articulation_points.clear(); // Xóa kết quả cũ

    // Duyệt qua tất cả các đỉnh. Nếu đỉnh chưa thăm, bắt đầu một DFS mới
    // Điều này đảm bảo xử lý tất cả các thành phần liên thông của đồ thị
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            find_articulation_points_dfs(i);
        }
    }

    // In kết quả
    cout << "Cac dinh khop (Articulation Points): ";
    if (articulation_points.empty()) {
        cout << "Khong co." << endl;
    } else {
        for (int point : articulation_points) {
            cout << point << " ";
        }
        cout << endl;
    }
}

int main() {
    // Ví dụ 1: Đồ thị đơn giản
    cout << "--- Vi du 1 ---" << endl;
    int n1 = 5; // So dinh
    adj.assign(n1, vector<int>());
    adj[0].push_back(1); adj[1].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);

    // Đồ thị là một đường thẳng: 0-1-2-3-4
    // Các đỉnh 1, 2, 3 là đỉnh khớp. Loại bỏ 1 ngắt 0 khỏi {2,3,4}. Loại bỏ 2 ngắt {0,1} khỏi {3,4}. Loại bỏ 3 ngắt {0,1,2} khỏi 4.
    // Các đỉnh 0 và 4 không phải là đỉnh khớp (đỉnh lá).

    find_articulation_points(n1);
    // Dự kiến output: Cac dinh khop (Articulation Points): 1 2 3

    cout << "\n--- Vi du 2 ---" << endl;
    // Ví dụ 2: Đồ thị phức tạp hơn (hình số 8 hoặc hai tam giác nối bằng 1 đỉnh)
    int n2 = 7; // So dinh
    adj.assign(n2, vector<int>());
    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); // Tam giác 0-1-2

    adj[2].push_back(3); adj[3].push_back(2); // Đỉnh 2 nối với 3
    adj[3].push_back(4); adj[4].push_back(3);
    adj[3].push_back(5); adj[5].push_back(3);
    adj[4].push_back(5); adj[5].push_back(4); // Tam giác 3-4-5

    adj[5].push_back(6); adj[6].push_back(5); // Đỉnh 5 nối với 6

    // Đồ thị: (0-1-2-0) --2-- (3-4-5-3) --5-- 6
    // Đỉnh 2: Loại bỏ 2 ngắt kết nối tam giác 0-1-2 với phần còn lại. -> Đỉnh khớp
    // Đỉnh 3: Loại bỏ 3 ngắt kết nối 2 với tam giác 3-4-5 và nhánh 5-6. -> Đỉnh khớp
    // Đỉnh 5: Loại bỏ 5 ngắt kết nối tam giác 3-4-5 và nhánh 5-6. -> Đỉnh khớp
    // Các đỉnh 0, 1, 4, 6 không phải là đỉnh khớp (đỉnh lá hoặc nằm trong cycle).

    find_articulation_points(n2);
    // Dự kiến output: Cac dinh khop (Articulation Points): 2 3 5

    cout << "\n--- Vi du 3 ---" << endl;
    // Ví dụ 3: Đồ thị không liên thông
    int n3 = 8;
    adj.assign(n3, vector<int>());
    // Thành phần 1: 0-1-2
    adj[0].push_back(1); adj[1].push_back(0);
    adj[1].push_back(2); adj[2].push_back(1);

    // Thành phần 2: 3-4-5-3
    adj[3].push_back(4); adj[4].push_back(3);
    adj[4].push_back(5); adj[5].push_back(4);
    adj[5].push_back(3); adj[3].push_back(5);

    // Thành phần 3: 6-7-6
    adj[6].push_back(7); adj[7].push_back(6);
    adj[7].push_back(6); // Cạnh lặp (vô hướng coi như 1 cạnh) - không ảnh hưởng thuật toán

    // Thành phần 1: Đỉnh 1 là đỉnh khớp.
    // Thành phần 2: Không có đỉnh khớp (là một cycle).
    // Thành phần 3: Không có đỉnh khớp (là một cycle 2 đỉnh).

    find_articulation_points(n3);
    // Dự kiến output: Cac dinh khop (Articulation Points): 1

    return 0;
}

Giải thích Code Minh Họa

Cấu trúc dữ liệu:
- adj: vector<vector<int>> biểu diễn danh sách kề của đồ thị. adj[i] chứa vector các đỉnh kề với đỉnh i.
- disc, low: vector<int> có kích thước n. disc[i] lưu thời điểm khám phá đỉnh i. low[i] lưu thời điểm khám phá sớm nhất có thể đạt được từ đỉnh i hoặc cây con của nó qua cạnh ngược.
- visited: vector<bool> đánh dấu đỉnh đã được thăm trong DFS hay chưa.
- timer: Biến đếm toàn cục, tăng lên mỗi khi một đỉnh mới được khám phá (disc được gán).
- articulation_points: set<int> lưu trữ các đỉnh được xác định là đỉnh khớp. set tự động đảm bảo mỗi đỉnh chỉ xuất hiện một lần.
Hàm find_articulation_points_dfs(int u, int parent):
- Đây là hàm DFS đệ quy chính. u là đỉnh hiện tại đang thăm, parent là đỉnh cha của u trong cây DFS.
- visited[u] = true;: Đánh dấu u đã được thăm.
- disc[u] = low[u] = timer++;: Gán thời điểm khám phá (disc) và khởi tạo low bằng disc. Tăng timer.
- children_count: Biến đếm số con trong cây DFS của đỉnh u. Chỉ cần cho trường hợp đỉnh u là gốc.
- Vòng lặp for (int v : adj[u]): Duyệt qua các đỉnh v kề với u.
- if (v == parent) continue;: Bỏ qua cạnh đi ngược lên cha trực tiếp trong cây DFS.
- if (visited[v]): Nếu v đã được thăm VÀ v != parent, thì (u, v) là cạnh ngược. Ta cập nhật low[u] = min(low[u], disc[v]). Từ u có thể đi ngược đến v (với disc[v]).
- else: Nếu v chưa thăm, (u, v) là cạnh cây.
  - children_count++;: Tăng số con của u.
  - find_articulation_points_dfs(v, u);: Gọi đệ quy với v là đỉnh hiện tại và u là cha.
  - low[u] = min(low[u], low[v]);: Quan trọng! Sau khi thăm xong cây con của v, low[v] chứa thời điểm sớm nhất reachable từ cây con của v. Ta cập nhật low[u] bằng min(low[u], low[v]) vì từ u có thể đi xuống v và từ đó reachable đến cùng thời điểm sớm nhất đó.
  - Kiểm tra đỉnh khớp:
    - if (parent == -1 && children_count > 1): Nếu u là gốc của cây DFS (parent == -1) và có nhiều hơn một con, nó là đỉnh khớp.
    - if (parent != -1 && low[v] >= disc[u]): Nếu u không phải gốc (parent != -1) và low[v] (thời điểm sớm nhất reachable từ cây con của v) lớn hơn hoặc bằng disc[u] (thời điểm khám phá u), thì u là đỉnh khớp. Điều này có nghĩa là không có đường nào từ cây con của v thoát lên "phía trên" u mà không đi qua u.
- articulation_points.insert(u);: Thêm đỉnh u vào tập kết quả nếu nó thỏa mãn một trong hai điều kiện trên.
Hàm find_articulation_points(int n):
- Hàm này khởi tạo các mảng và biến cần thiết.
- Nó lặp qua tất cả các đỉnh từ 0 đến n-1.
- if (!visited[i]): Nếu đỉnh i chưa được thăm, nó là khởi đầu của một thành phần liên thông mới (hoặc thành phần liên thông đầu tiên). Ta gọi find_articulation_points_dfs(i) để bắt đầu DFS từ đây. Tham số cha mặc định là -1 cho gốc của cây DFS này.
- Sau khi lặp hết, set articulation_points chứa tất cả các đỉnh khớp.
- In kết quả.
Hàm main():
- Thiết lập các ví dụ đồ thị khác nhau bằng cách xây dựng danh sách kề adj.
- Gọi find_articulation_points() cho từng ví dụ.
- In tiêu đề rõ ràng cho mỗi ví dụ.

Thuật toán Tarjan này có độ phức tạp thời gian là O(V + E) và độ phức tạp không gian là O(V + E), vì mỗi đỉnh và mỗi cạnh được thăm không quá hai lần trong quá trình DFS, và ta cần lưu trữ đồ thị cùng với các mảng disc, low, visited.

Bài tập ví dụ:

Vượt Sông

Trong một chuyến phiêu lưu mới, FullHouse Dev đứng trước một con sông với dòng chảy xiết. Để đến được đích, họ cần vượt qua con sông này. May mắn thay, trên sông có một số tảng đá mà họ có thể sử dụng để di chuyển. Với tinh thần không lùi bước, FullHouse Dev bắt đầu tính toán cách vượt sông an toàn nhất.

Bài toán

Con sông nằm trên trục \(X\) và được giới hạn bởi các tọa độ \(Y\). Mỗi tảng đá được xác định bởi tâm và bán kính của nó. FullHouse Dev hiện đang đứng ở bờ sông. Họ không thể nhảy giữa các tảng đá nhưng có thể di chuyển từ tảng đá này sang tảng đá khác nếu chúng có điểm giao nhau. Nhiệm vụ là xác định xem liệu có thể vượt sông bằng cách sử dụng các tảng đá hay không, và nếu có thì cần ít nhất bao nhiêu tảng đá.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
Với mỗi test case:
- Dòng đầu tiên chứa số nguyên \(N\) - số lượng tảng đá
- \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x_i\), \(y_i\), \(r_i\) trong đó \((x_i, y_i)\) là tọa độ tâm của tảng đá và \(r_i\) là bán kính của nó
- Dòng cuối cùng chứa hai số nguyên \(Y_1\) và \(Y_2\) - giới hạn trên và dưới của con sông

OUTPUT FORMAT:

Với mỗi test case, in ra số lượng tảng đá tối thiểu cần dùng để vượt sông. Nếu không thể vượt sông, in ra \(-1\).

Ràng buộc:

\(1 \leq T \leq 100\)
\(1 \leq N \leq 1000\)
\(-1000 \leq x_i, y_i \leq 1000\)
\(1 \leq r_i \leq 1000\)
\(-1000 \leq Y_1, Y_2 \leq 1000\)

Ví dụ

INPUT

OUTPUT

Giải thích

Từ bờ sông, FullHouse Dev có thể bước lên tảng đá đầu tiên. Sau đó, họ có thể vượt sông trực tiếp hoặc di chuyển đến tảng đá thứ hai rồi vượt sông. Lưu ý rằng họ không thể sử dụng tảng đá thứ ba vì nó nằm ngoài tầm với từ các tảng đá khác. Tuyệt vời! Đây là hướng dẫn giải bài "Vượt Sông" sử dụng cấu trúc dữ liệu và giải thuật, tập trung vào ý tưởng chính mà không cung cấp code hoàn chỉnh:

Phân tích bài toán:
- Bài toán yêu cầu tìm đường đi ngắn nhất (số tảng đá ít nhất) từ một "vị trí bắt đầu" đến một "vị trí kết thúc".
- Di chuyển chỉ có thể thực hiện giữa các tảng đá giao nhau.
- "Vị trí bắt đầu" là bờ sông (một trong hai giới hạn Y1 hoặc Y2). "Vị trí kết thúc" là bờ sông còn lại.
- Đây là một bài toán tìm đường đi ngắn nhất trong một đồ thị không trọng số, phù hợp với thuật toán BFS (Breadth-First Search).
Xây dựng mô hình đồ thị:
- Các đỉnh (nodes): Mỗi tảng đá sẽ là một đỉnh trong đồ thị. Ta có N đỉnh tương ứng với N tảng đá.
- Các cạnh (edges): Có một cạnh giữa hai tảng đá i và j nếu hai tảng đá này giao nhau. Hai hình tròn (tảng đá) có tâm (x1, y1) bán kính r1 và (x2, y2) bán kính r2 giao nhau nếu khoảng cách giữa hai tâm d nhỏ hơn hoặc bằng tổng hai bán kính r1 + r2. Khoảng cách d có thể tính bằng công thức Euclid: d = sqrt((x1-x2)^2 + (y1-y2)^2). Tuy nhiên, để tránh dùng số thực và căn bậc hai, ta có thể so sánh bình phương khoảng cách với bình phương tổng bán kính: (x1-x2)^2 + (y1-y2)^2 <= (r1+r2)^2. Lưu ý sử dụng kiểu dữ liệu long long khi tính bình phương để tránh tràn số.
- Nguồn (source): FullHouse Dev bắt đầu từ một bờ sông. Một tảng đá i được coi là "có thể tiếp cận từ bờ sông bắt đầu" nếu vòng tròn của nó chạm hoặc vượt qua giới hạn Y của bờ sông đó. Giả sử hai bờ sông là Y_min và Y_max (đã sắp xếp Y1, Y2). Tảng đá i (tâm (x_i, y_i), bán kính r_i) có thể tiếp cận từ bờ Y_min nếu y_i - r_i <= Y_min.
- Đích (destination): Họ đã vượt sông nếu một tảng đá i chạm hoặc vượt qua giới hạn Y của bờ sông kết thúc. Tảng đá i chạm bờ Y_max nếu y_i + r_i >= Y_max.
Thuật toán BFS:
- Bước 1 (Khởi tạo):
  - Xác định Y_min = min(Y1, Y2) và Y_max = max(Y1, Y2).
  - Khởi tạo một hàng đợi (queue) cho BFS.
  - Khởi tạo một mảng/set visited để theo dõi các tảng đá đã thăm (ban đầu tất cả là false).
  - Duyệt qua tất cả các tảng đá. Nếu một tảng đá i thỏa mãn điều kiện "có thể tiếp cận từ bờ Y_min" (y_i - r_i <= Y_min):
    - Đưa tảng đá i vào hàng đợi cùng với số bước là 1 (vì đây là tảng đá đầu tiên). Ví dụ: queue.push({i, 1}).
    - Đánh dấu tảng đá i là đã thăm (visited[i] = true).
    - Lưu ý: Nếu ngay tảng đá đầu tiên này mà nó đã "chạm đến bờ Y_max" (y_i + r_i >= Y_max), thì đáp án là 1. Có thể kiểm tra và trả về 1 ngay tại đây hoặc để BFS xử lý (BFS sẽ tìm ra 1 là đáp án ngắn nhất).
- Bước 2 (Duyệt BFS):
  - Trong khi hàng đợi chưa rỗng:
    - Lấy phần tử đầu tiên ra khỏi hàng đợi: (current_stone_index, num_stones_used).
    - Kiểm tra xem tảng đá hiện tại có "chạm đến bờ Y_max" không (stones[current_stone_index].y + stones[current_stone_index].r >= Y_max). Nếu có, ta đã tìm thấy đường đi ngắn nhất (do BFS), trả về num_stones_used.
    - Nếu chưa chạm đích, tìm các "tảng đá lân cận": Duyệt qua tất cả các tảng đá khác j (từ 0 đến N-1):
      - Nếu tảng đá j chưa được thăm (!visited[j]) và tảng đá current_stone_index giao nhau với tảng đá j (kiểm tra điều kiện giao nhau (x_curr-x_j)^2 + (y_curr-y_j)^2 <= (r_curr+r_j)^2):
        
        Đánh dấu tảng đá j là đã thăm (visited[j] = true).
        
        Đưa tảng đá j vào hàng đợi với số bước tăng lên 1: queue.push({j, num_stones_used + 1}).
- Bước 3 (Kết quả):
  - Nếu vòng lặp BFS kết thúc mà chưa tìm thấy đường đi (hàm chưa trả về), điều đó có nghĩa là không thể vượt sông. Trả về -1.
Cấu trúc chương trình:
- Đọc số lượng test case T.
- Lặp lại T lần:
  - Đọc N.
  - Lưu trữ thông tin về N tảng đá (ví dụ: vector of struct/tuple/pair).
  - Đọc Y1, Y2.
  - Thực hiện thuật toán BFS như mô tả ở trên.
  - In kết quả.

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

Comments

There are no comments at the moment.