Đếm cầu trọng yếu
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một đơn đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Một cạnh được gọi là cầu nếu khi xóa cạnh đó đi, số thành phần liên thông của đồ thị tăng lên. Hãy đếm số lượng cạnh cầu trong đồ thị.
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$, $u \ne v$, không có cạnh song song).
Dữ liệu ra
- In 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 |
| 4 4 1 2 2 3 3 4 4 1 |
0 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Community Discussion