Đỉnh khớp và cạnh cầu

Algorithms Buổi 65-66 — Mock HSG Graphs
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$.

Draft saved