Cầu Và Khớp
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho đồ thị vô hướng liên thông gồm N đỉnh và M cạnh. Hãy đếm số cầu (bridge) và số đỉnh khớp (articulation point) trong đồ thị.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên N M (1 ≤ N ≤ 100000, 1 ≤ M ≤ 200000).
M dòng tiếp theo, mỗi dòng chứa hai số nguyên u v (1 ≤ u, v ≤ N) mô tả một cạnh vô hướng. Đồ thị không có cạnh bội hay tự vòng.
Dữ liệu ra
In ra hai số nguyên trên một dòng: số cầu và số đỉnh khớp, cách nhau bởi dấu cách.
Ví dụ
| Input | Output |
|---|---|
| 7 7\n1 2\n2 3\n3 1\n3 4\n4 5\n5 6\n6 7 | 4 3 |
Giới hạn
- 1 ≤ N ≤ 100000
- 1 ≤ M ≤ 200000
- Đồ thị liên thông, không có cạnh bội hay tự vòng.
Community Discussion