Cầu Và Khớp

Buổi 52 — Mock Contest Phase 2
Points
25
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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.
Draft saved