Cầu nối trọng yếu
Points
90
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một đồ thị vô hướng liên thông gồm $N$ đỉnh và $M$ cạnh (có thể có đa cạnh). Một cạnh được gọi là cầu nếu việc xóa bỏ nó làm đồ thị mất tính liên thông.
Bạn được phép thêm tối đa một cạnh mới nối hai đỉnh bất kỳ trong đồ thị. Hãy tìm số lượng cầu ít nhất có thể còn lại trong đồ thị sau khi thêm cạnh.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($2 \le N \le 10^5$, $N - 1 \le M \le 2 \cdot 10^5$).
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$, $u \neq v$) mô tả một cạnh vô hướng.
Kết quả
In ra một số nguyên duy nhất là số lượng cầu ít nhất còn lại.
Subtasks
- Subtask 1 (30%): Đồ thị là một cây ($M = N - 1$).
- Subtask 2 (30%): $N \le 2000, M \le 5000$.
- Subtask 3 (40%): Không có ràng buộc thêm.
Ví dụ
| Input | Output |
|---|---|
| 6 6 1 2 2 3 3 1 3 4 4 5 4 6 |
1 |
Community Discussion