🕸️ Cheatsheet: Cầu & Khớp (Bridge & Articulation Point)

📘 Giới thiệu

Trong lý thuyết đồ thị, khớp (articulation point) là một đỉnh mà nếu bị loại bỏ sẽ làm tăng số thành phần liên thông của đồ thị.

Cầu (bridge) là một cạnh mà nếu bị loại bỏ sẽ làm đồ thị bị chia tách.

🔧 Ứng dụng

• Thiết kế mạng không có điểm lỗi đơn (single point of failure).
• Tìm điểm yếu trong hệ thống liên kết.
• Phân tích mạng máy tính, mạng xã hội.
• Chia đồ thị thành biconnected components.
• Phân tích cấu trúc liên thông mạnh/yếu.

⏱️ Độ phức tạp

• Thời gian: O(V + E) với DFS.
• Không gian: O(V + E)

✅ Ưu điểm

• Cài đặt hiệu quả với DFS.
• Tìm tất cả cầu & khớp trong một lượt duyệt.
• Ứng dụng rộng trong thực tiễn & thuật toán chia đồ thị.

❌ Nhược điểm

• Không áp dụng cho đồ thị có hướng (phải dùng biến thể khác).
• Cần xử lý kỹ khi có cạnh song song (multiedge) hoặc đồ thị không liên thông.

📌 C++ Code (DFS cho cầu và khớp)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];
int tin[MAXN], low[MAXN], timer;
bool is_articulation[MAXN];
vector<pair<int, int>> bridges;

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

    for (int v : adj[u]) {
        if (v == parent) continue;

        if (tin[v]) {
            low[u] = min(low[u], tin[v]);
        } else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u])
                bridges.emplace_back(u, v);
            if (low[v] >= tin[u] && parent != -1)
                is_articulation[u] = true;
            ++children;
        }
    }

    if (parent == -1 && children > 1)
        is_articulation[u] = true;
}

void find_bridges_and_cutpoints(int n) {
    timer = 0;
    fill(tin, tin + n + 1, 0);
    fill(low, low + n + 1, 0);
    fill(is_articulation, is_articulation + n + 1, false);
    bridges.clear();

    for (int i = 1; i <= n; ++i)
        if (!tin[i])
            dfs(i, -1);
}

📌 Tối ưu khi dùng

• Duyệt đồ thị không liên thông: nhớ chạy DFS cho từng thành phần.
• Có thể lưu biconnected components trong stack để tái sử dụng.
• Xử lý trùng cạnh: dùng set<pair<int, int>> nếu cần loại trừ cạnh song song.

🧭 Khi nào dùng?

📚 Tham khảo

• CP-Algorithms - Bridges
• CP-Algorithms - Articulation Points
• Bài tập: CSES Graph Algorithms / SPOJ SUBMERGE / VNOI QBRECT