Block-Cut Tree: Thành phần Song liên thông Đỉnh
Cho một đồ thị vô hướng liên thông gồm N đỉnh và M cạnh. Xây dựng Block-Cut Tree của đồ thị và đếm số lượng khối (Biconnected Components / Blocks) cùng số lượng đỉnh khớp (articula…
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: stl, pointers, trees and graphs.
Nội dung đề bài
Mô tả bài toán
Mô tả bài toán
Cho một đồ thị vô hướng liên thông gồm N đỉnh và M cạnh. Xây dựng Block-Cut Tree của đồ thị và đếm số lượng khối (Biconnected Components / Blocks) cùng số lượng đỉnh khớp (articulation points / cut vertices).
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 tiên gồm 2 số nguyên N, M (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000).
- M dòng tiếp theo, mỗi dòng gồm 2 số nguyên u, v mô tả một cạnh vô hướng ($1 ≤ u, v ≤ N, u
e v$).
Output
- Dòng 1: In ra số đỉnh khớp (cut vertices).
- Dòng 2: In ra số khối song liên thông đỉnh (blocks).
Ràng buộc
- Thời gian: 1.0s. Bộ nhớ: 256MB.
Ví dụ 1
Input
5 5
1 2
2 3
3 1
3 4
4 5Output
2
3Giải thích
Dữ liệu đầu vào mẫu và kết quả tương ứng theo đúng đặc tả giải thuật.
Ví dụ 2
Input
3 3
1 2
2 3
3 1Output
0
1Giải thích
Dữ liệu kiểm thử trường hợp biên và kết quả trả về tương ứ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.