Đếm thành phần song liên thông
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Một thành phần song liên thông đỉnh (vertex-biconnected component - BCC) là một đồ thị con liên thông cực đại không có đỉnh khớp. Trong bài toán này, ta chỉ xét các thành phần song liên thông có chứa ít nhất một cạnh (mỗi cạnh của đồ thị thuộc về đúng một thành phần song liên thông).
Cho đơn đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Hãy đếm số lượng thành phần song liên thông (có ít nhất một cạnh) và tìm số lượng đỉnh lớn nhất trong một thành phần song liên thông. Nếu $M = 0$, in ra 0 0.
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, u \ne v$).
Dữ liệu ra
- Hai số nguyên cách nhau bởi dấu cách: số lượng thành phần song liên thông và kích thước (số đỉnh) lớn nhất của một thành phần.
Ví dụ
| Input | Output |
|---|---|
| 5 5 1 2 2 3 3 1 3 4 4 5 |
3 3 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Community Discussion