Đếm cầu xung yếu
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề 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$.
Community Discussion