Đỉnh cô lập
Đề bài
Mô tả
Cho một đồ thị vô hướng gồm đỉnh và cạnh. Đồ thị không có khuyên (cạnh nối một đỉnh với chính nó) và không có cạnh bội (hai cạnh cùng nối một cặp đỉnh; do đồ thị vô hướng nên cặp và được coi là trùng nhau).
Một đỉnh được gọi là cô lập nếu không có cạnh nào nối đỉnh đó với bất kỳ đỉnh nào khác.
Hãy tìm số đỉnh cô lập nhỏ nhất và lớn nhất có thể có, xét trên tất cả các đồ thị vô hướng gồm đúng đỉnh và cạnh.
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và .
Dữ liệu đảm bảo luôn tồn tại ít nhất một đồ thị vô hướng không khuyên, không cạnh bội với đỉnh và cạnh.
Dữ liệu ra
Một dòng chứa hai số nguyên: số đỉnh cô lập nhỏ nhất và số đỉnh cô lập lớn nhất.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 2 | 0 1 | Với các cạnh và thì không có đỉnh nào cô lập. Với các cạnh và thì đỉnh cô lập, và không thể có nhiều hơn đỉnh cô lập vì cạnh cần ít nhất đỉnh. |
| 3 1 | 1 1 | Một cạnh chỉ phủ được đúng đỉnh, nên luôn còn đúng đỉnh cô lập. |
| 100000 49997 | 6 99683 | Trải đều cạnh ra thì phủ được đỉnh, còn đỉnh cô lập. Dồn hết cạnh vào một đồ thị đầy đủ thì cần đỉnh vì . |
Bình luận