Đây là bài toán tìm cầu khớp cơ bản đầu tiên cần biết. Ý tưởng thuật toán như sau (nên xem thêm Tài liệu chuyên tin quyển 1): Bắt chước ý tưởng từ thuật toán Tarjan, gọi num[u] là số thứ tự đỉnh duyệt đến, low[u] là giá trị thứ tự nhỏ nhất mà trong cây DFS gốc u.

Tạo thêm mảng pa[u] là đỉnh cha của u trong khi duyệt, pa[u] = 0 khi u là chốt của cây DFS (đỉnh được duyệt đầu tiên).

Ta thực hiện định chiều DFS trong quá trình duyệt dfs tương tự thuật toán Tarjan. Bây giờ vấn đề đặt ra cạnh nào là cầu, đỉnh nào là khớp.

• Với cầu: Giả sử với cạnh (u,v) với u là cha trực tiếp của v trong quá trình dfs (u = pa[v]). Nếu như từ v theo các cung đã định hướng, không có cách lên được u thì (u,v) là cầu của đồ thị low[v] >= num[v]

• Với khớp: Xét hai trường hợp:

  • Khi u là chốt của một cây DFS: (pa[u] = 0) nếu nó có hai nhánh con trong cây DFS đã định hướng thì khi hủy u sẽ tăng số TPLT => u là khớp
  • Khi u không là chốt: (pa[u] > 0) Gọi v là đỉnh con của u thì nếu từ v không có cách đi theo cung định hướng lên được các đỉnh trên u thì u lúc này là khớp low[v] >= num[u]. (cách kiểm tra: duyệt v = 1->n, sau đó xét u là pa[v]).