Mạng Cáp Dự Phòng Hai Kết Nối

Buổi 44 — Cầu & Khớp Graphs Trees
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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.

Draft saved