Đỉnh khớp và cạnh cầu
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho đồ thị vô hướng đơn gồm $N$ đỉnh và $M$ cạnh.
- Đỉnh khớp là đỉnh mà khi xóa nó (cùng các cạnh liên thuộc) sẽ làm tăng số thành phần liên thông của đồ thị.
- Cạnh cầu là cạnh mà khi xóa nó sẽ 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 và số lượng cạnh cầu của đồ thị.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$.
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả một cạnh.
Dữ liệu ra
In ra hai số nguyên: số lượng đỉnh khớp và số lượng cạnh cầu.
Ví dụ
| Input | Output |
|---|---|
| 5 5 1 2 2 3 1 3 3 4 4 5 |
2 2 |
| 4 4 1 2 2 3 3 4 4 1 |
0 0 |
Giới hạn
$1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Community Discussion