trang chủ / bài tập / isolvert

Đỉnh cô lập

Đề bài

Mô tả

Cho một đồ thị vô hướng gồm n đỉnh và m 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 (1,2)(2,1) đượ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ấtlớn nhất có thể có, xét trên tất cả các đồ thị vô hướng gồm đúng n đỉnh và m cạnh.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên nm.

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 n đỉnh và m 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

  • 1n105
  • 0mn(n1)2

Ví dụ

Input Output Giải thích
4 2 0 1 Với các cạnh (1,2)(3,4) thì không có đỉnh nào cô lập. Với các cạnh (1,2)(1,3) thì đỉnh 4 cô lập, và không thể có nhiều hơn 1 đỉnh cô lập vì 2 cạnh cần ít nhất 3 đỉnh.
3 1 1 1 Một cạnh chỉ phủ được đúng 2 đỉnh, nên luôn còn đúng 1 đỉnh cô lập.
100000 49997 6 99683 Trải đều 49997 cạnh ra thì phủ được 99994 đỉnh, còn 6 đỉnh cô lập. Dồn hết cạnh vào một đồ thị đầy đủ thì cần 317 đỉnh vì (3162)=49770<4999750086=(3172).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0