Bridge và Articulation Point

Wiki › Thuật toán › Thuật toán đồ thị

huunguyen · Last updated 8, Tháng 4, 2026, 15:25

Bridge (cầu) là cạnh mà khi xóa đi làm đồ thị mất liên thông. Articulation Point (khớp) là đỉnh mà khi xóa đi (cùng các cạnh kề) làm đồ thị mất liên thông. Cả hai tìm được trong $O (V + E)$ bằng DFS của Tarjan.

Ý tưởng

Trong DFS tree, định nghĩa:

disc[u]: thời điểm DFS khám phá $u$ .
low[u]: thời điểm khám phá nhỏ nhất có thể đạt được từ cây con gốc $u$ (kể cả qua back edge).

Bridge: Cạnh $(u, v)$ với $v$ là con của $u$ trong DFS tree là bridge khi $low [v] > disc [u]$ — không có back edge nào từ cây con $v$ lên $u$ hoặc tổ tiên của $u$ .

Articulation Point: $u$ là khớp khi:

$u$ là gốc DFS và có $\geq 2$ con trong DFS tree, hoặc
$u$ không phải gốc và tồn tại con $v$ với $low [v] \geq disc [u]$ .

Cài đặt

const int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
int disc[MAXN], low[MAXN], timer_val = 0;
bool is_ap[MAXN];
vector<pair<int,int>> bridges;

void dfs(int u, int parent) {
    disc[u] = low[u] = ++timer_val;
    int children = 0;

    for (int v : adj[u]) {
        if (v == parent) continue;   // bỏ qua cạnh cha (đồ thị vô hướng)

        if (!disc[v]) {
            children++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            // Kiểm tra bridge
            if (low[v] > disc[u])
                bridges.push_back({u, v});

            // Kiểm tra articulation point
            if (parent == -1 && children > 1) is_ap[u] = true;
            if (parent != -1 && low[v] >= disc[u]) is_ap[u] = true;
        } else {
            // Back edge
            low[u] = min(low[u], disc[v]);
        }
    }
}

// Gọi:
// for (int i = 1; i <= n; i++) if (!disc[i]) dfs(i, -1);

Lưu ý với đa cạnh: Thay if (v == parent) bằng kiểm tra index cạnh để tránh đi ngược đúng cạnh đó (không phải cạnh song song).

// Lưu cạnh theo index
vector<pair<int,int>> adj[MAXN];  // {neighbor, edge_id}

void dfs(int u, int par_edge) {
    disc[u] = low[u] = ++timer_val;
    for (auto [v, eid] : adj[u]) {
        if (eid == par_edge) continue;
        if (!disc[v]) {
            dfs(v, eid);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) bridges.push_back({u, v});
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
}

Biconnected Components

Các cạnh nằm giữa hai articulation point liên tiếp tạo thành biconnected component (BCC). Có thể xây block-cut tree từ BCCs và articulation points — hữu ích cho bài toán 2-connectivity.

// Tìm BCCs bằng stack cạnh
stack<pair<int,int>> edge_stack;

void dfs_bcc(int u, int p) {
    disc[u] = low[u] = ++timer_val;
    for (int v : adj[u]) {
        if (!disc[v]) {
            edge_stack.push({u, v});
            dfs_bcc(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= disc[u]) {
                // Pop một BCC
                vector<pair<int,int>> bcc;
                while (edge_stack.top() != make_pair(u, v)) {
                    bcc.push_back(edge_stack.top()); edge_stack.pop();
                }
                bcc.push_back(edge_stack.top()); edge_stack.pop();
                // bcc chứa tất cả cạnh trong BCC này
            }
        } else if (v != p) {
            low[u] = min(low[u], disc[v]);
            if (disc[v] < disc[u]) edge_stack.push({u, v});
        }
    }
}

Độ phức tạp

$O (V + E)$ — một lần DFS duy nhất.

Khi nào dùng?

Tìm điểm yếu trong mạng lưới (single point of failure).
Bài toán 2-edge-connected hoặc 2-vertex-connected components.
Tiền xử lý cho các thuật toán trên cây (block-cut tree).

Bình luận

Không có bình luận tại thời điểm này.