Thành Phần Liên Thông 2-Đỉnh (Block-Cut Tree)
Cho một đồ thị vô hướng G = (V, E) gồm N đỉnh và M cạnh.
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: Tarjan's Articulation Points, Stack-based BCC.
Nội dung đề bài
Mô tả bài toán
Cho một đồ thị vô hướng G = (V, E) gồm N đỉnh và M cạnh.
Một đỉnh khớp (articulation point / cut vertex) là đỉnh mà khi xóa nó cùng các cạnh liên thuộc sẽ làm tăng số thành phần liên thông của đồ thị. Một thành phần liên thông 2-đỉnh (Biconnected Component - BCC / Block) là một đồ thị con cực đại không chứa bất kỳ đỉnh khớp nào (giữa hai đỉnh bất kỳ trong block luôn có ít nhất 2 đường đi độc lập về đỉnh).
Hãy xác định:
- Số lượng đỉnh khớp của đồ thị G.
- Số lượng khối thành phần liên thông 2-đỉnh (Blocks) 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 đầu chứa hai số nguyên N và M (1 ≤ N ≤ 105, 0 ≤ M ≤ 2 · 105).
- M dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v (1 ≤ u, v ≤ N, u ≠ v) biểu diễn một cạnh.
Output
- In ra hai số nguyên cách nhau bởi dấu cách: số đỉnh khớp và số khối BCC.
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 định dạng và miền giá trị được mô tả.
Ví dụ 1
Input
5 5
1 2
2 3
3 1
3 4
4 5Output
2 3Giải thích
Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.
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.