Bridge và Articulation Point

Cầu (bridge) là cạnh mà khi xóa đi sẽ làm tăng số thành phần liên thông của đồ thị (tức làm mất liên thông). Đỉnh khớp (articulation point / cut vertex) là đỉnh mà khi xóa đi (cùng mọi cạnh kề nó) cũng làm mất liên thông. Cả hai đều là "điểm yếu" của mạng lưới — nơi một sự cố đơn lẻ làm sập kết nối.

Cách ngây thơ: thử xóa từng cạnh (hoặc từng đỉnh) rồi chạy lại DFS/BFS kiểm tra liên thông, tốn $O(E·(V+E))$ — quá chậm với $V,E$ lên tới ${10}^5$. Thuật toán Tarjan dựa trên giá trị low-link chỉ cần một lần DFS duy nhất, đạt $O(V+E)$.

Ý tưởng / Trực giác

Khi chạy DFS trên đồ thị vô hướng liên thông, ta thu được một cây DFS (DFS tree). Mọi cạnh của đồ thị rơi vào đúng hai loại:

• Cạnh cây (tree edge): cạnh DFS dùng để đi xuống một đỉnh chưa thăm.
• Cạnh ngược (back edge): cạnh nối một đỉnh tới tổ tiên của nó trong cây DFS. (Trên đồ thị vô hướng không có cạnh chéo/cạnh xuôi.)

Cạnh ngược chính là "dây an toàn": nó cho phép cây con leo ngược lên trên mà không phải đi qua cạnh cây nối nó với cha. Ta định nghĩa hai mốc thời gian:

• disc[u]: thời điểm DFS lần đầu khám phá $u$ (số thứ tự thăm).
• low[u]: disc nhỏ nhất mà $u$ hoặc bất kỳ đỉnh nào trong cây con gốc $u$ có thể chạm tới, nếu được dùng tối đa một cạnh ngược. Nói cách khác: leo cao nhất tới đâu trong cây DFS nếu xuất phát từ cây con của $u$.

Công thức cập nhật khi đang ở $u$, xét hàng xóm $v$:

$$\text{low}[u]=min(\text{low}[u],\underset{v\text{ là con}}{\underbrace{\text{low}[v]}},\underset{(u,v)\text{ là cạnh ngược}}{\underbrace{\text{disc}[v]}})$$

Vì sao xác định được cầu? Xét cạnh cây $(u,v)$ với $v$ là con. Cạnh này là cầu khi và chỉ khi không có cách nào từ cây con gốc $v$ leo ngược lên $u$ hoặc cao hơn $u$ ngoài việc đi lại đúng cạnh $(u,v)$. Điều đó tương đương:

$$\text{low}[v]>\text{disc}[u]$$

Nếu $\text{low}[v]\le \text{disc}[u]$, tồn tại một cạnh ngược nối cây con $v$ tới $u$ hoặc tổ tiên của $u$, tạo thành chu trình bao quanh cạnh $(u,v)$ — xóa cạnh vẫn còn đường vòng, nên không phải cầu.

Vì sao xác định được đỉnh khớp? Có hai trường hợp:

1. $u$ là gốc DFS: $u$ là khớp khi và chỉ khi nó có $\ge 2$ con trong cây DFS. Vì các cây con của gốc chỉ có thể nối với nhau qua chính gốc (nếu nối được bằng cạnh ngược thì chúng đã thuộc cùng một cây con). Xóa gốc làm các cây con rời nhau.
2. $u$ không phải gốc: $u$ là khớp khi tồn tại con $v$ thỏa $\text{low}[v]\ge \text{disc}[u]$ — cây con $v$ không leo được lên trên $u$, nên xóa $u$ thì cây con $v$ bị cô lập khỏi phần còn lại.

Lưu ý dấu khác nhau: cầu dùng dấu $>$ (chặt), khớp dùng dấu $\ge$ (cho phép bằng). Vì một đỉnh có thể là khớp mà cạnh xuống nó không phải cầu (khi cây con leo đúng tới $u$ nhưng không cao hơn).

Ví dụ chạy tay

Xét đồ thị 5 đỉnh, các cạnh: 1-2, 1-3, 2-3, 3-4, 4-5.

        1 --- 2
         \   /
          \ /
           3
           |
           4
           |
           5

Tam giác $\{1,2,3\}$ liên kết chặt; phần $3\text{-}4\text{-}5$ là một "đuôi" thẳng. Trực giác: cạnh 3-4 và 4-5 là cầu; đỉnh khớp là 3 (cắt đuôi khỏi tam giác) và 4 (cắt 5 khỏi phần trên).

DFS bắt đầu từ đỉnh 1 (gốc), đi 1→2→3→4→5. Bảng disc/low sau khi xử lý xong (số trong ngoặc là thứ tự thăm):

Bây giờ kiểm tra từng cạnh cây (con → cha):

cạnh (4,5): low[5]=5 > disc[4]=4  → CẦU ✓ ;  low[5]=5 >= disc[4]=4 → 4 là KHỚP ✓
cạnh (3,4): low[4]=4 > disc[3]=3  → CẦU ✓ ;  low[4]=4 >= disc[3]=3 → 3 là KHỚP ✓
cạnh (2,3): low[3]=1 > disc[2]=2 ? KHÔNG (1<2) → không cầu
cạnh (1,2): low[2]=1 > disc[1]=1 ? KHÔNG → không cầu ; gốc 1 chỉ có 1 con → không khớp

Kết quả: Cầu = {(3,4), (4,5)}, Khớp = {3, 4} — đúng như trực giác. Để ý đỉnh 5 (lá) và đỉnh 1 (gốc 1 con) không phải khớp.

Cài đặt

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

const int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
int disc[MAXN], low[MAXN], timer_val = 0;
bool is_ap[MAXN];                       // is_ap[u] = u có phải đỉnh khớp
vector<pair<int,int>> bridges;          // danh sách cầu

void dfs(int u, int parent) {
    disc[u] = low[u] = ++timer_val;     // gán disc và low ban đầu = thời điểm thăm
    int children = 0;                   // số con trong cây DFS (dùng cho gốc)

    for (int v : adj[u]) {
        if (v == parent) continue;      // bỏ qua cạnh nối thẳng tới cha

        if (!disc[v]) {                 // v chưa thăm → (u,v) là cạnh cây
            children++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);          // hấp thụ low của cây con

            if (low[v] > disc[u])                  // không leo lên được tới u → CẦU
                bridges.push_back({u, v});

            // điều kiện đỉnh khớp:
            if (parent == -1 && children > 1) is_ap[u] = true;   // gốc, >=2 con
            if (parent != -1 && low[v] >= disc[u]) is_ap[u] = true;
        } else {
            // v đã thăm và không phải cha → cạnh ngược: cập nhật bằng disc[v]
            low[u] = min(low[u], disc[v]);
        }
    }
}

int main() {
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b; scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    // gọi cho từng thành phần liên thông; gốc đánh dấu parent = -1
    for (int i = 1; i <= n; i++)
        if (!disc[i]) dfs(i, -1);

    // ... in bridges và các i có is_ap[i] = true
    return 0;
}

Xử lý đa cạnh (multi-edge): nếu đồ thị có thể có nhiều cạnh giữa cùng một cặp đỉnh, điều kiện v == parent là sai — hai cạnh song song $u\text{-}v$ không bao giờ là cầu, nhưng cách trên sẽ bỏ qua cả hai và báo nhầm. Hãy chặn theo chỉ số cạnh thay vì theo đỉnh cha:

vector<pair<int,int>> adj2[MAXN];       // {hàng xóm, edge_id}

void dfs_multi(int u, int par_edge) {
    disc[u] = low[u] = ++timer_val;
    for (auto [v, eid] : adj2[u]) {
        if (eid == par_edge) continue;  // chỉ bỏ đúng cạnh vừa đi xuống
        if (!disc[v]) {
            dfs_multi(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]);
        }
    }
}

Độ phức tạp

• Thời gian: $O(V+E)$. Mỗi đỉnh được thăm đúng một lần (nhờ kiểm tra disc[v]), và mỗi cạnh kề được duyệt đúng hai lần (một lần từ mỗi đầu). Mọi thao tác cập nhật low là $O(1)$. Không có bước nào lặp lại đồ thị, nên tổng chi phí tuyến tính theo kích thước đồ thị.
• Bộ nhớ: $O(V+E)$. Danh sách kề chiếm $O(V+E)$; các mảng disc, low, is_ap chiếm $O(V)$; ngăn xếp đệ quy sâu tối đa $O(V)$.

⚠️ Lỗi thường gặp

• Tràn ngăn xếp (stack overflow) do DFS đệ quy sâu. Với đồ thị ${10}^5$ đỉnh là một đường thẳng, độ sâu đệ quy lên ${10}^5$ có thể làm tràn stack mặc định. Cách tránh: tăng giới hạn stack, hoặc viết DFS bằng stack thủ công (khử đệ quy).
• Nhầm dấu > và >=. Cầu là low[v] > disc[u] (dấu chặt); đỉnh khớp là low[v] >= disc[u]. Đảo nhầm sẽ báo thiếu/thừa. Nhớ: cầu cần "leo hẳn lên trên $u$" còn khớp chỉ cần "không vượt qua $u$".
• Quên trường hợp gốc DFS khi tìm khớp. Gốc là khớp chỉ khi có $\ge 2$ con; nếu áp dụng điều kiện low[v] >= disc[u] cho gốc thì gốc có 1 con cũng bị báo nhầm là khớp (vì luôn có một con $v$ với low[v] >= disc[root]).
• Cập nhật low bằng low[v] thay vì disc[v] ở cạnh ngược. Khi gặp cạnh ngược tới đỉnh đã thăm $v$, phải dùng low[u] = min(low[u], disc[v]). Dùng low[v] có thể "leo" quá xa qua một cạnh ngược khác, làm sai kết quả cầu/khớp.
• Xử lý đa cạnh bằng v == parent. Như đã nêu, với cạnh bội phải dùng chỉ số cạnh, không dùng đỉnh cha — nếu không hai cạnh song song bị báo nhầm là cầu.
• Quên đồ thị không liên thông. Phải gọi DFS từ mọi đỉnh chưa thăm (for i: if (!disc[i]) dfs(i,-1)), nếu không sẽ bỏ sót các thành phần khác.
• Đánh số thời gian bắt đầu từ 0 mà dùng disc[v]==0 để kiểm tra "chưa thăm". Khi đó đỉnh thăm đầu tiên có disc = 0, bị tưởng nhầm là chưa thăm. Hãy dùng ++timer_val (bắt đầu từ 1) như code trên, hoặc khởi tạo disc bằng $-1$.

Biến thể / Mở rộng

• Thành phần song liên thông cạnh (2-edge-connected components): sau khi tìm hết cầu, xóa các cầu rồi tìm thành phần liên thông; mỗi thành phần là một khối "không có cầu". Nén mỗi thành phần thành một đỉnh sẽ thu được cây cầu (bridge tree).
• Thành phần song liên thông đỉnh (biconnected components, BCC): các cạnh giữa hai đỉnh khớp liên tiếp gộp thành một BCC; có thể trích bằng một ngăn xếp cạnh trong cùng lần DFS. Từ BCC và các đỉnh khớp dựng được block-cut tree — công cụ mạnh cho các bài 2-liên-thông.
• Định hướng cạnh: mọi đồ thị vô hướng 2-edge-connected (không có cầu) đều có thể định hướng thành đồ thị liên thông mạnh (định lý Robbins).

Bài tập luyện

• Các Con Đường Cần Thiết (necesroads) — (Kỳ cựu) Liệt kê toàn bộ cầu của đồ thị — bài áp dụng trực tiếp công thức low[v] > disc[u].
• Các Thành Phố Cần Thiết (nececities) — (Kỳ cựu) Liệt kê toàn bộ đỉnh khớp — luyện đúng hai điều kiện khớp (gốc và không-gốc).
• Cạnh trên Chu trình Đơn Duy nhất (simcyc) — (Chuyên gia) Loại bỏ cầu rồi phân tích cấu trúc thành phần song liên thông để tìm cạnh thuộc đúng một chu trình đơn — kết hợp cầu với BCC.
• Đẩy Hộp (pushabox) — (Chuyên gia) Bài khó dùng thành phần song liên thông / block-cut tree làm tiền xử lý cho BFS trạng thái — nâng cao về 2-liên-thông.