Đếm cầu xung yếu

Buổi 44 — Cầu & Khớp
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh (có thể không liên thông và có thể chứa cạnh song song). Một cạnh được gọi là cầu (bridge) nếu việc xóa bỏ cạnh đó làm tăng số thành phần liên thông của đồ thị.

Hãy đếm số lượng cầu có trong đồ thị đã cho.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5, 0 \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$) mô tả một cạnh vô hướng nối giữa $u$ và $v$.
Dữ liệu ra
  • Một số nguyên duy nhất là số lượng cầu của đồ thị.
Ví dụ
Input Output
5 5
1 2
2 3
3 1
3 4
4 5
2
Giới hạn
  • $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Draft saved