Thuật toán Tarjan tìm khớp và cầu trên đồ thị vô hướng
Hạ tầng mạng viễn thông của AI Empire Academy gồm N trạm máy chủ (1 ≤ N ≤ 105) và M đường cáp quang nối trực tiếp (1 ≤ M ≤ 2 · 105). Đồ thị là vô hướng, có thể không…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: graph representation, dfs, std vector.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu cây tìm kiếm theo chiều sâu (DFS Tree), phân biệt cạnh trên cây (Tree Edge) và cạnh ngược (Back Edge).
- Cài đặt thuật toán Tarjan với hai mảng mốc thời gian:
tin[u](thời điểm thăm) vàlow[u](thời điểm nhỏ nhất vươn tới được qua tối đa 1 cạnh ngược). - Nhận biết điều kiện cầu (
low[v] > tin[u]) và đỉnh khớp (low[v] >= tin[u]).
Mô tả bài toán
Hạ tầng mạng viễn thông của AI Empire Academy gồm N trạm máy chủ (1 ≤ N ≤ 105) và M đường cáp quang nối trực tiếp (1 ≤ M ≤ 2 · 105). Đồ thị là vô hướng, có thể không liên thông, không có khuyên (self-loop) nhưng có thể có đa cạnh.
Một đường cáp (u, v) được gọi là Cầu nếu ngắt nó sẽ làm tăng số thành phần liên thông của mạng. Một trạm máy chủ u được gọi là Khớp nếu ngắt nó (cùng toàn bộ các đường cáp nối vào nó) sẽ làm tăng số thành phần liên thông.
Hãy đếm số lượng đỉnh khớp và số lượng cạnh cầu của đồ thị.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng 1: Gồm 2 số nguyên N và M (1 ≤ N ≤ 105, 0 ≤ M ≤ 2 · 105).
- M dòng tiếp theo: Mỗi dòng gồm 2 số nguyên u, v (1 ≤ u, v ≤ N, u ≠ v) đại diện cho một đường cáp giữa trạm u và v.
Output
- In ra hai số nguyên trên một dòng cách nhau bởi dấu cách: Số lượng đỉnh khớp và số lượng cạnh cầu.
Ràng buộc
- 1 ≤ N ≤ 105.
- 0 ≤ M ≤ 2 · 105.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
5 5
1 2
2 3
3 1
3 4
4 5Output
2 2
*Giải thích:*
- Các khớp là đỉnh 3 và đỉnh 4 (tổng cộng 2 khớp).
- Các cầu là cạnh (3, 4) và cạnh (4, 5) (tổng cộng 2 cầu).Ví dụ 2
Input
4 4
1 2
2 3
3 4
4 1Output
0 0
*Giải thích:* Đồ thị tạo thành chu trình 4 đỉnh, không có trạm hay đường cáp nào bị ngắt mà làm đứt mạng.Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.