Thành phần 2-cạnh liên thông
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một đồ thị vô hướng liên thông gồm $N$ đỉnh và $M$ cạnh. Một thành phần 2-cạnh liên thông (2-ECC) là một tập đỉnh cực đại sao cho giữa hai đỉnh bất kỳ trong tập luôn tồn tại ít nhất hai đường đi không chung cạnh nào (tức không có cầu nào nằm trong thành phần đó).
Hãy tìm:
- Số lượng thành phần 2-cạnh liên thông của đồ thị.
- Số cạnh ít nhất cần thêm vào đồ thị để toàn bộ đồ thị trở thành một thành phần 2-cạnh liên thông duy nhất (không còn cầu nào).
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5, N - 1 \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$). Dữ liệu đảm bảo đồ thị liên thông.
Dữ liệu ra
- Hai số nguyên cách nhau bởi dấu cách: số thành phần 2-cạnh liên thông và số cạnh ít nhất cần thêm.
Ví dụ
| Input | Output |
|---|---|
| 5 4 1 2 1 3 1 4 1 5 |
5 2 |
Giới hạn
- $1 \le N \le 10^5$, $N - 1 \le M \le 2 \cdot 10^5$.
Community Discussion