Xoá ít nhất bao nhiêu cạnh để đồ thị thành rừng
Một rừng là đồ thị không chứa chu trình, tức là mỗi thành phần liên thông của nó là một
Tiến độ của tôi ở bài này
Điểm và code bạn nộp đượ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: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Một rừng là đồ thị không chứa chu trình, tức là mỗi thành phần liên thông của nó là một cây. Muốn biến một mạng lưới lộn xộn thành rừng, ta phải xoá đi một số cạnh. Câu hỏi trung tâm là phải xoá ít nhất bao nhiêu cạnh.
Yêu cầu
Cho đồ thị vô hướng gồm n đỉnh đánh số 1..n và m cạnh. Hãy in ra số cạnh nhỏ nhất cần xoá sao cho đồ thị còn lại không có chu trình. Đồ thị có thể rời rạc, và mỗi thành phần liên thông có k đỉnh chỉ giữ được nhiều nhất k - 1 cạnh mà không tạo chu trình.
Quy ước nộp bài
Nộp tệp solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Chỉ in đúng một số nguyên, không in thêm gì khác. Chỉ dùng thư viện chuẩn C++17.
Input
- Dòng đầu tiên: hai số nguyên n, m (1 <= n <= 8, 0 <= m <= 12).
- m dòng tiếp theo: mỗi dòng hai số nguyên u, v (1 <= u, v <= n, u != v) mô tả
một cạnh vô hướng giữa u và v. Giữa hai đỉnh có nhiều nhất một cạnh.
- Nếu m = 0 thì không có dòng cạnh nào.
Output
In ra stdout một số nguyên duy nhất: số cạnh tối thiểu phải xoá. Đáp án luôn là số không âm.
Ràng buộc
- Đồ thị đơn, vô hướng, có thể rời rạc.
- Đồ thị đã là rừng thì đáp án là 0.
- Mỗi bộ dữ liệu có thời gian chạy 1 giây.
Ví dụ 1
Input
5 5
1 2
2 3
3 1
3 4
4 5
Output
1
Ví dụ 2
Input
4 3
1 2
2 3
3 4
Output
0
Giải thích
Dữ liệu vào:
Cả 5 đỉnh nằm trong một thành phần liên thông, nên một cây trên 5 đỉnh chỉ giữ được 4 cạnh. Đang có 5 cạnh, vậy phải xoá 1 cạnh (chẳng hạn xoá cạnh 1-3 để phá tam giác 1-2-3). Kết quả là:
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.
