Phân Tán Mạng Khi Cô Lập Một Nút
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Một mạng máy tính liên thông gồm $N$ máy chủ (đánh số từ $1$ đến $N$) và $M$ kết nối hai chiều giữa các máy chủ. Nếu một máy chủ $v$ gặp sự cố và bị gỡ bỏ hoàn toàn khỏi mạng (kéo theo mọi đường kết nối gắn với $v$ bị ngắt), $N - 1$ máy chủ còn lại sẽ tách thành một hoặc nhiều thành phần liên thông rời nhau.
Gọi $f(v)$ là kích thước (số lượng máy chủ) của thành phần liên thông lớn nhất còn lại sau khi gỡ bỏ máy chủ $v$. Hãy tìm giá trị nhỏ nhất của $f(v)$ và chỉ số máy chủ $v$ đạt giá trị đó (nếu có nhiều máy chủ cùng đạt giá trị nhỏ nhất, chọn máy chủ có chỉ số nhỏ nhất).
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($2 \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$) biểu thị một kết nối.
Dữ liệu ra
In ra trên một dòng hai số nguyên: giá trị nhỏ nhất của $f(v)$ và chỉ số máy chủ $v$ tương ứng.
Ví dụ
| Input | Output |
|---|---|
| 6 6 1 2 2 3 1 3 3 4 4 5 4 6 |
3 3 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion