Bài 21.5. Bài tập cơ bản về cầu và khớp

Chào mừng bạn trở lại với series về Cấu trúc dữ liệu và Giải thuật (CTDL & GT)! Hôm nay, chúng ta sẽ đi sâu vào một khía cạnh thú vị của lý thuyết đồ thị: khả năng kết nối (connectivity). Đặc biệt, chúng ta sẽ tìm hiểu về hai khái niệm quan trọng giúp đánh giá sự vững chắc của một đồ thị: Cầu (Bridge) và Khớp (Articulation Point hay Cut Vertex).

Trong thế giới thực, đồ thị có thể mô tả mạng lưới đường giao thông, hệ thống mạng máy tính, mạng xã hội,... Việc xác định "điểm yếu" trong mạng lưới này là cực kỳ quan trọng. Cầu và Khớp chính là những điểm yếu đó. Nếu loại bỏ một cầu hoặc một khớp, đồ thị có thể bị chia thành nhiều phần không liên thông, gây ảnh hưởng nghiêm trọng đến toàn bộ hệ thống.

Hãy cùng khám phá chi tiết hơn về chúng nhé!

Cầu (Bridge) là gì?

Một cầu trong đồ thị vô hướng là một cạnh mà nếu loại bỏ nó, số lượng 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ầu là một cạnh "thiết yếu" cho sự liên thông giữa hai phần của đồ thị.

Hãy tưởng tượng một mạng lưới đường bộ: một cây cầu bắc qua sông nối hai khu vực. Nếu cây cầu đó sập (tức là cạnh bị loại bỏ), việc đi lại giữa hai khu vực đó có thể trở nên bất khả thi, làm tăng số lượng "mảnh" đất liền không thể tiếp cận nhau trực tiếp. Đó chính là một cây cầu (bridge) trong đồ thị giao thông.

Làm thế nào để tìm Cầu?

Phương pháp phổ biến và hiệu quả để tìm tất cả các cầu trong một đồ thị là sử dụng thuật toán Tìm kiếm theo chiều sâu (DFS). Ý tưởng chính là theo dõi thời gian khám phá các đỉnh và "điểm thấp nhất" mà từ một đỉnh hoặc bất kỳ đỉnh nào trong cây con DFS của nó có thể truy cập được thông qua các cạnh ngược (back-edges).

Chúng ta cần duy trì các thông tin sau trong quá trình DFS:

disc[u]: Thời điểm (thứ tự) đỉnh u được khám phá lần đầu tiên.
low[u]: Thời điểm khám phá sớm nhất (discovery time nhỏ nhất) của đỉnh mà đỉnh u hoặc bất kỳ đỉnh nào trong cây con DFS có gốc tại u có thể đạt tới thông qua các cạnh trong cây DFS hoặc các cạnh ngược.

Thuật toán hoạt động như sau:

Bắt đầu DFS từ một đỉnh bất kỳ. Duy trì một bộ đếm thời gian toàn cục tăng dần. Khi thăm đỉnh u lần đầu tiên, gán disc[u] = low[u] = time++.

Đối với mỗi đỉnh kề v của u:

Nếu v là đỉnh cha của u trong cây DFS, bỏ qua cạnh (u, v) (đây là cạnh ngược tầm thường).
Nếu v đã được thăm (tức là visited[v] là true): Đây là một cạnh ngược (u, v). Cạnh này nối u với một đỉnh đã được thăm. Cập nhật low[u] = min(low[u], disc[v]). Điều này có nghĩa là từ u hoặc cây con của nó, ta có thể đi ngược về đỉnh v đã được thăm, và đỉnh v này được khám phá vào thời điểm disc[v].
Nếu v chưa được thăm: Đây là một cạnh cây (u, v). Đặt v là con của u (parent[v] = u), thực hiện DFS trên v. Sau khi cuộc gọi đệ quy DFS(v) kết thúc, cập nhật low[u] = min(low[u], low[v]). Điều này là để truyền giá trị low nhỏ nhất từ cây con của v lên cho u.

Sau khi cập nhật low[u] từ low[v], chúng ta kiểm tra điều kiện để xác định cầu:

Cạnh (u, v) là một cầu NẾU low[v] > disc[u].

Tại sao lại là điều kiện này? Điều kiện low[v] > disc[u] có nghĩa là đỉnh v và tất cả các đỉnh trong cây con của nó không thể kết nối (bằng cạnh cây hoặc cạnh ngược) với đỉnh u hoặc bất kỳ đỉnh nào được khám phá trước u (có disc nhỏ hơn disc[u]). Do đó, cạnh (u, v) là đường "duy nhất" (trong ngữ cảnh kết nối ngược) để cây con của v kết nối với phần còn lại của đồ thị bên ngoài cây con đó thông qua u. Nếu loại bỏ (u, v), cây con của v sẽ bị tách rời khỏi u và những đỉnh được thăm trước u.

Ví dụ minh họa C++ tìm Cầu

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

using namespace std;

vector<vector<int>> adj; // Danh sách kề
vector<int> disc;      // Thời điểm khám phá
vector<int> low;       // Điểm thấp nhất có thể truy cập
vector<int> parent;    // Đỉnh cha trong cây DFS
vector<bool> visited;   // Đánh dấu đã thăm
int timer;             // Bộ đếm thời gian

// Hàm DFS để tìm cầu
void findBridgesDFS(int u) {
    visited[u] = true;
    disc[u] = low[u] = timer++;

    for (int v : adj[u]) {
        // Nếu v là cha của u, bỏ qua
        if (v == parent[u]) continue;

        if (visited[v]) {
            // Nếu v đã được thăm, đây là cạnh ngược
            low[u] = min(low[u], disc[v]);
        } else {
            // Nếu v chưa được thăm, đây là cạnh cây
            parent[v] = u;
            findBridgesDFS(v);

            // Cập nhật low[u] sau khi thăm xong cây con của v
            low[u] = min(low[u], low[v]);

            // KIỂM TRA CẦU: Nếu low[v] > disc[u], cạnh (u, v) là cầu
            if (low[v] > disc[u]) {
                cout << "Canh (" << u << ", " << v << ") la mot cau\n";
            }
        }
    }
}

// Hàm chính để tìm cầu trong toàn bộ đồ thị
void findBridges(int n) {
    timer = 0;
    visited.assign(n, false);
    disc.assign(n, -1);
    low.assign(n, -1);
    parent.assign(n, -1);

    // Duyệt qua tất cả các đỉnh để xử lý đồ thị không liên thông
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            findBridgesDFS(i);
        }
    }
}

int main() {
    int n = 5; // Số đỉnh
    int m = 5; // Số cạnh

    adj.resize(n);

    // Ví dụ đồ thị: 0-1, 1-2, 2-0, 1-3, 3-4
    // Đây là đồ thị có 2 thành phần liên thông: {0,1,2} và {3,4}
    // Cạnh nối 2 thành phần này là (1,3) - đây là cầu.
    // Thành phần {0,1,2} là một chu trình, không có cầu.
    adj[0].push_back(1); adj[1].push_back(0);
    adj[1].push_back(2); adj[2].push_back(1);
    adj[2].push_back(0); adj[0].push_back(2);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[3].push_back(4); adj[4].push_back(3);

    cout << "Tim cau trong do thi:\n";
    findBridges(n);

    // Một ví dụ khác: Đồ thị đường thẳng 0-1-2-3
    cout << "\nTim cau trong do thi duong thang 0-1-2-3:\n";
    n = 4;
    adj.assign(n, 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);
    findBridges(n);


    return 0;
}

Giải thích Code:

adj: Biểu diễn đồ thị bằng danh sách kề. adj[i] chứa danh sách các đỉnh kề với đỉnh i.
disc, low, parent, visited: Các vector để lưu trữ thông tin cần thiết cho thuật toán DFS như đã mô tả ở trên. timer là bộ đếm thời gian toàn cục.
findBridgesDFS(int u): Hàm thực hiện DFS bắt đầu từ đỉnh u.
- Đánh dấu u đã thăm, khởi tạo disc[u] và low[u] bằng timer hiện tại, sau đó tăng timer.
- Duyệt qua các đỉnh kề v của u.
- Bỏ qua nếu v là đỉnh cha (để tránh xử lý cạnh cây theo chiều ngược lại như cạnh ngược).
- Nếu v đã thăm, cập nhật low[u]. Đây là trường hợp cạnh ngược. low[u] có thể bằng disc[v] nếu cạnh ngược đi thẳng tới v.
- Nếu v chưa thăm, đặt parent[v] = u, gọi đệ quy findBridgesDFS(v). Sau khi đệ quy trả về, cập nhật low[u] bằng min(low[u], low[v]) để mang giá trị low nhỏ nhất từ cây con của v lên u.
- Quan trọng nhất là kiểm tra if (low[v] > disc[u]). Nếu điều kiện này đúng, cạnh (u, v) là một cầu và chúng ta in ra thông báo.
findBridges(int n): Hàm bao bọc để khởi tạo các vector và bắt đầu DFS từ tất cả các đỉnh chưa thăm. Điều này đảm bảo thuật toán hoạt động đúng với cả đồ thị không liên thông.
main(): Thiết lập một vài đồ thị ví dụ và gọi hàm findBridges để tìm cầu.

Kết quả chạy ví dụ 1:

Tim cau trong do thi:
Canh (1, 3) la mot cau
Canh (3, 4) la mot cau

Tim cau trong do thi duong thang 0-1-2-3:
Canh (0, 1) la mot cau
Canh (1, 2) la mot cau
Canh (2, 3) la mot cau

Như bạn thấy, trong ví dụ đầu tiên, cạnh (1, 3) và (3, 4) là cầu (đúng như dự đoán). Trong ví dụ thứ hai, đồ thị đường thẳng, tất cả các cạnh đều là cầu, vì loại bỏ bất kỳ cạnh nào cũng chia đồ thị thành hai thành phần.

Khớp (Articulation Point / Cut Vertex) là gì?

Một khớp (hoặc điểm cắt) trong đồ thị vô hướng là một đỉnh mà nếu loại bỏ nó (cùng với tất cả các cạnh liên thuộc với nó), số lượng thành phần liên thông của đồ thị sẽ tăng lên. Một khớp là một "điểm nút" quan trọng, nếu nó bị "hỏng" thì mạng lưới có thể bị chia cắt.

Tiếp tục với ví dụ mạng lưới đường bộ: một thành phố đóng vai trò là trung tâm giao thông quan trọng, nơi nhiều tuyến đường chính hội tụ. Nếu thành phố đó bị phong tỏa hoàn toàn (loại bỏ đỉnh), giao thông giữa các khu vực khác có thể bị ảnh hưởng nghiêm trọng hoặc ngừng trệ. Thành phố đó chính là một khớp.

Làm thế nào để tìm Khớp?

Chúng ta sử dụng cùng khung thuật toán DFS với disc và low như khi tìm cầu. Tuy nhiên, điều kiện để một đỉnh u là khớp hơi khác so với điều kiện để một cạnh là cầu.

Một đỉnh u là khớp NẾU thỏa mãn một trong hai điều kiện sau:

u là gốc (root) của cây DFS, và nó có ít nhất hai cây con trong cây DFS. Nếu loại bỏ gốc và các cạnh của nó, các cây con này sẽ bị tách rời khỏi nhau và khỏi gốc.
u không phải là gốc của cây DFS, và tồn tại ít nhất một con v của u trong cây DFS sao cho low[v] >= disc[u]. Điều kiện này có nghĩa là cây con gốc v không thể sử dụng cạnh ngược để kết nối với u hoặc bất kỳ tổ tiên nào của u (có thời gian khám phá nhỏ hơn disc[u]). Do đó, nếu loại bỏ u, cây con gốc v sẽ bị tách khỏi phần còn lại của đồ thị ở phía trên u.

Lưu ý sự khác biệt với điều kiện tìm cầu (low[v] > disc[u]): Đối với khớp (trường hợp không phải gốc), điều kiện là low[v] >= disc[u]. Dấu bằng (=) được bao gồm vì nếu low[v] == disc[u], điều đó có nghĩa là điểm sớm nhất mà cây con của v có thể truy cập thông qua cạnh ngược là chính đỉnh u. Nếu loại bỏ u, con đường này bị cắt, và cây con của v sẽ bị tách khỏi phần còn lại.

Ví dụ minh họa C++ tìm Khớp

#include <iostream>
#include <vector>
#include <algorithm>
#include <set> // Sử dụng set để lưu khớp, tránh trùng lặp và tự sắp xếp

using namespace std;

vector<vector<int>> adj; // Danh sách kề
vector<int> disc;      // Thời điểm khám phá
vector<int> low;       // Điểm thấp nhất có thể truy cập
vector<int> parent;    // Đỉnh cha trong cây DFS
vector<bool> visited;   // Đánh dấu đã thăm
int timer;             // Bộ đếm thời gian
set<int> articulationPoints; // Lưu trữ các khớp

// Hàm DFS để tìm khớp
void findArticulationPointsDFS(int u) {
    visited[u] = true;
    disc[u] = low[u] = timer++;

    int children = 0; // Đếm số con của u trong cây DFS (quan trọng cho trường hợp gốc)

    for (int v : adj[u]) {
        // Nếu v là cha của u, bỏ qua
        if (v == parent[u]) continue;

        if (visited[v]) {
            // Nếu v đã được thăm, đây là cạnh ngược
            low[u] = min(low[u], disc[v]);
        } else {
            // Nếu v chưa được thăm, đây là cạnh cây
            parent[v] = u;
            children++; // Tăng số con của u
            findArticulationPointsDFS(v);

            // Cập nhật low[u] sau khi thăm xong cây con của v
            low[u] = min(low[u], low[v]);

            // KIỂM TRA KHỚP (TRƯỜNG HỢP KHÔNG PHẢI GỐC):
            // Nếu u không phải gốc VÀ tồn tại con v sao cho low[v] >= disc[u]
            if (parent[u] != -1 && low[v] >= disc[u]) {
                articulationPoints.insert(u);
            }
        }
    }

    // KIỂM TRA KHỚP (TRƯỜNG HỢP GỐC):
    // Nếu u là gốc VÀ có ít nhất 2 con
    if (parent[u] == -1 && children > 1) {
        articulationPoints.insert(u);
    }
}

// Hàm chính để tìm khớp trong toàn bộ đồ thị
void findArticulationPoints(int n) {
    timer = 0;
    visited.assign(n, false);
    disc.assign(n, -1);
    low.assign(n, -1);
    parent.assign(n, -1);
    articulationPoints.clear();

    // Duyệt qua tất cả các đỉnh để xử lý đồ thị không liên thông
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            findArticulationPointsDFS(i);
        }
    }

    cout << "Cac khop (articulation points) trong do thi:\n";
    if (articulationPoints.empty()) {
        cout << "Khong co khop nao.\n";
    } else {
        for (int ap : articulationPoints) {
            cout << ap << " ";
        }
        cout << "\n";
    }
}

int main() {
    int n = 5; // Số đỉnh
    int m = 5; // Số cạnh

    adj.resize(n);

    // Ví dụ đồ thị: 0-1, 1-2, 2-0, 1-3, 3-4
    // Khớp: Đỉnh 1 (loại bỏ 1 sẽ tách {0,2} khỏi {3,4})
    // Đỉnh 3 (loại bỏ 3 sẽ tách {0,1,2} khỏi {4})
    adj[0].push_back(1); adj[1].push_back(0);
    adj[1].push_back(2); adj[2].push_back(1);
    adj[2].push_back(0); adj[0].push_back(2);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[3].push_back(4); adj[4].push_back(3);

    findArticulationPoints(n);

    // Ví dụ khác: Đồ thị đường thẳng 0-1-2-3
    // Khớp: Đỉnh 1, 2
    cout << "\nTim khop trong do thi duong thang 0-1-2-3:\n";
    n = 4;
    adj.assign(n, 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);
    findArticulationPoints(n);

    // Ví dụ khác: Đồ thị hình sao 0 - {1,2,3,4}
    // Khớp: Đỉnh 0
    cout << "\nTim khop trong do thi hinh sao (0 la trung tam): 0-1, 0-2, 0-3, 0-4\n";
    n = 5;
    adj.assign(n, vector<int>());
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[0].push_back(3); adj[3].push_back(0);
    adj[0].push_back(4); adj[4].push_back(0);
    findArticulationPoints(n);


    return 0;
}

Giải thích Code:

Phần khai báo biến và cấu trúc dữ liệu tương tự như tìm cầu, nhưng thay vì in cầu, chúng ta lưu các khớp tìm được vào một set<int> gọi là articulationPoints. set giúp lưu trữ các đỉnh duy nhất và tự động sắp xếp.
findArticulationPointsDFS(int u): Hàm DFS.
- Thêm biến children để đếm số lượng con trực tiếp của u trong cây DFS. Điều này là cần thiết để xử lý trường hợp u là gốc.
- Vòng lặp duyệt qua các đỉnh kề v của u tương tự như tìm cầu.
- Khi thăm một con v (chưa thăm), tăng children.
- Sau khi gọi đệ quy findArticulationPointsDFS(v) và cập nhật low[u] = min(low[u], low[v]), chúng ta kiểm tra điều kiện khớp cho trường hợp u không phải là gốc: if (parent[u] != -1 && low[v] >= disc[u]). Nếu đúng, u là một khớp.
- Sau vòng lặp duyệt qua tất cả các kề của u, chúng ta kiểm tra điều kiện khớp cho trường hợp u là gốc: if (parent[u] == -1 && children > 1). Nếu đúng, u là một khớp.
- Các khớp tìm được được thêm vào articulationPoints.
findArticulationPoints(int n): Hàm bao bọc khởi tạo và gọi DFS, sau đó in ra các khớp đã lưu trong set.
main(): Thiết lập các đồ thị ví dụ và gọi hàm findArticulationPoints.

Kết quả chạy ví dụ 1:

Cac khop (articulation points) trong do thi:
1 3

Tim khop trong do thi duong thang 0-1-2-3:
1 2

Tim khop trong do thi hinh sao (0 la trung tam): 0-1, 0-2, 0-3, 0-4
0

Kết quả khớp với phân tích: Đỉnh 1 và 3 là khớp trong đồ thị đầu tiên, đỉnh 1 và 2 là khớp trong đồ thị đường thẳng, và đỉnh 0 là khớp duy nhất trong đồ thị hình sao.

Mối liên hệ giữa Cầu và Khớp

Có một mối liên hệ chặt chẽ giữa cầu và khớp:

Nếu một cạnh (u, v) là một cầu, thì ít nhất một trong hai đỉnh u hoặc v thường là một khớp.
Ngoại lệ là khi đỉnh đó có bậc bằng 1. Ví dụ, trong đồ thị 0-1-2, cạnh (1,2) là cầu. Đỉnh 1 là khớp, nhưng đỉnh 2 thì không (vì loại bỏ đỉnh 2 chỉ loại bỏ nó và cạnh (1,2), không làm tăng số thành phần liên thông của phần còn lại 0-1).

Cả hai thuật toán tìm cầu và khớp đều dựa trên cùng một ý tưởng DFS và sử dụng các giá trị disc và low, chỉ khác nhau ở điều kiện kiểm tra cuối cùng. Độ phức tạp thời gian của cả hai thuật toán là O(V + E), trong đó V là số đỉnh và E là số cạnh, vì mỗi cạnh và mỗi đỉnh được thăm hằng số lần trong quá trình DFS.

Bài tập ví dụ:

Tâm trí hủy diệt

Trong một vụ án mới, thám tử FullHouse Dev đang điều tra một kẻ tình nghi có tên Rhezo. Rhezo sở hữu một đồ thị và có xu hướng phá hoại đặc biệt - anh ta thường xóa các đỉnh của đồ thị để tạo ra nhiều thành phần liên thông hơn.

Bài toán

Rhezo có một đồ thị với \(N\) đỉnh và \(M\) cạnh. Với tâm trí hủy diệt của mình, anh ta thường xóa một số đỉnh (và tất nhiên cả các cạnh nối với đỉnh đó). Rhezo sẽ đưa ra \(Q\) truy vấn. Mỗi truy vấn được biểu thị bằng một số nguyên \(X\), nghĩa là anh ta sẽ xóa đỉnh \(X\). Rhezo sẽ cảm thấy hài lòng nếu đồ thị mới (sau khi xóa đỉnh) có số thành phần liên thông nhiều hơn đồ thị ban đầu.

INPUT FORMAT:

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\), thể hiện có một cạnh nối giữa đỉnh \(A\) và đỉnh \(B\).
Dòng tiếp theo chứa một số nguyên \(Q\) - số lượng truy vấn.
\(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(X\) thể hiện đỉnh bị xóa trong truy vấn đó.

OUTPUT FORMAT:

Với mỗi truy vấn, nếu Rhezo hài lòng (số thành phần liên thông tăng lên), in ra "Satisfied" và số cạnh bị xóa (cách nhau bởi dấu cách).
Ngược lại, in ra "Not Satisfied".

Ràng buộc:

\(1 \leq N \leq 10^5\)
\(1 \leq M \leq 10^5\)
\(1 \leq Q \leq N\)
\(1 \leq A, B, X \leq N\)

Ví dụ

INPUT

OUTPUT

Not Satisfied
Satisfied 2
Satisfied 3
Not Satisfied
Not Satisfied

Giải thích

Ở truy vấn thứ hai, khi xóa đỉnh 2, đồ thị bị chia thành hai thành phần liên thông. Một thành phần chỉ có {1} và thành phần còn lại gồm {3,4,5}. Số cạnh bị xóa là 2. Hướng giải bài "Tâm trí hủy diệt" bằng C++ một cách ngắn gọn:

Bài toán yêu cầu xác định xem việc xóa một đỉnh X khỏi đồ thị ban đầu có làm tăng số thành phần liên thông (TPLT) hay không, và đếm số cạnh bị xóa. Việc xóa đỉnh X làm tăng số TPLT khi và chỉ khi X là một đỉnh khớp (articulation point) trong đồ thị ban đầu. Số cạnh bị xóa khi xóa đỉnh X chính là bậc của đỉnh X trong đồ thị ban đầu.

Vì mỗi truy vấn độc lập và xét trên đồ thị ban đầu, chúng ta có thể xử lý ngoại tuyến (offline) hoặc tính toán trước thông tin cần thiết. Cách hiệu quả nhất là tính toán tất cả các đỉnh khớp của đồ thị ban đầu trước khi xử lý các truy vấn.

Các bước thực hiện:

Đọc đồ thị và tính toán ban đầu:
- Đọc số đỉnh N, số cạnh M.
- Xây dựng biểu diễn đồ thị, ví dụ bằng danh sách kề (adjacency list).
- Trong quá trình đọc cạnh, đồng thời tính toán và lưu trữ bậc của mỗi đỉnh.
Tìm tất cả các đỉnh khớp trong đồ thị ban đầu:
- Sử dụng thuật toán tìm đỉnh khớp dựa trên DFS (ví dụ: thuật toán của Tarjan).
- Cần các mảng/biến: visited (hoặc tương tự), discovery time (disc), lowest back-edge time (low), và parent trong cây DFS.
- Duyệt qua tất cả các đỉnh từ 1 đến N. Nếu đỉnh chưa được thăm, bắt đầu một phiên DFS từ đỉnh đó.
- Trong quá trình DFS, áp dụng quy tắc xác định đỉnh khớp:
  - Đối với gốc của cây DFS: là đỉnh khớp nếu có ít nhất 2 con trong cây DFS.
  - Đối với đỉnh u không phải gốc, và v là con của u trong cây DFS: u là đỉnh khớp nếu low[v] >= disc[u].
- Lưu trữ các đỉnh khớp tìm được, ví dụ trong một mảng boolean is_articulation_point hoặc một tập hợp (set). Đảm bảo xử lý đúng các thành phần liên thông khác nhau của đồ thị.
Xử lý các truy vấn:
- Đọc số lượng truy vấn Q.
- Với mỗi truy vấn, đọc đỉnh X cần xóa:
  - Kiểm tra xem đỉnh X có được đánh dấu là đỉnh khớp ở bước 2 hay không (dựa vào mảng boolean/set is_articulation_point).
  - Nếu is_articulation_point[X] là true: In ra "Satisfied" và bậc của đỉnh X đã tính ở bước 1.
  - Nếu is_articulation_point[X] là false: In ra "Not Satisfied".

Độ phức tạp:

Đọc đồ thị và tính bậc: O(N + M).
Tìm tất cả đỉnh khớp: O(N + M) (một lần DFS trên toàn bộ đồ thị).
Xử lý Q truy vấn: O(1) cho mỗi truy vấn (tra cứu trong mảng boolean/set), tổng O(Q).
Tổng cộng: O(N + M + Q), phù hợp với ràng buộc (10^5).

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

Comments

There are no comments at the moment.