Thuật toán Tarjan tìm Điểm khớp (Articulation Points) và Cầu (Bridges)

Mục tiêu kiến thức

• Hiểu cấu trúc cây DFS (DFS Spanning Tree) và các cạnh ngược (Back-edges).
• Cài đặt thời điểm thăm tin / disc và giá trị liên kết thấp nhất low.
• Phát hiện các cạnh cầu (Bridges) và đỉnh khớp (Articulation Points) trong thời gian O(V + E).

Mô tả bài toán

Cho đồ thị vô hướng gồm n đỉnh (từ 0 đến n - 1) và danh sách các cạnh edges.

Viết hàm find_bridges_and_articulation_points(n: int, edges: list[tuple[int, int]]) -> tuple[list[tuple[int, int]], list[int]]:

• Tìm tất cả các Cạnh cầu (Bridges): cạnh mà khi loại bỏ nó, số thành phần liên thông của đồ thị tăng lên.
• Mỗi cạnh được chuẩn hóa dạng (min(u, v), max(u, v)).
• Danh sách các cạnh cầu được sắp xếp tăng dần theo thứ tự từ điển.
• Tìm tất cả các Điểm khớp (Articulation Points): đỉnh mà khi loại bỏ nó cùng các cạnh nối với nó, số thành phần liên thông của đồ thị tăng lên.
• Danh sách các đỉnh khớp được sắp xếp tăng dần.
• Hỗ trợ đồ thị không liên thông.

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.