Đếm khớp trọng yếu
Points
20
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). Một đỉnh được gọi là đỉnh khớp (articulation point) nếu việc xóa bỏ đỉnh đó (cùng các cạnh kề với nó) làm tăng số thành phần liên thông của đồ thị.
Hãy đếm số lượng đỉnh khớp của đồ 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$) mô tả một cạnh vô hướng.
Dữ liệu ra
- Một số nguyên duy nhất là số lượng đỉnh khớp 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