Mạng Cáp Dự Phòng Hai Kết Nối
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Một hệ thống viễn thông gồm $N$ trạm phát sóng (đánh số từ $1$ đến $N$) và $M$ đường cáp truyền dẫn hai chiều. Ban đầu toàn bộ mạng liên thông và giữa hai trạm có thể tồn tại nhiều hơn một đường cáp song song.
Một đường cáp được xem là điểm yếu chí mạng nếu khi đường cáp đó bị đứt, hệ thống bị chia cắt thành hai phần không liên thông với nhau (tức cạnh đó là cầu). Để gia cố mạng lưới sao cho không còn bất kỳ đường cáp nào là cầu, các kỹ sư muốn lắp đặt thêm một số đường cáp mới giữa các cặp trạm.
Hãy xác định số lượng đường cáp mới ít nhất cần lắp đặt thêm.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($1 \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 \ne v$) mô tả một đường cáp hiện có.
Dữ liệu ra
In ra một số nguyên duy nhất là số đường cáp mới tối thiểu cần thêm.
Ví dụ
| Input | Output |
|---|---|
| 4 3 1 2 2 3 3 4 |
1 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion