BUILDROAD - Xây đường
Dữ liệu vào: Standard input
Dữ liệu ra: Standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte

Yêu cầu: Byteland là 1 đất nước gồm n thành phố và m con đường nối giữa các thành phố. Mục tiêu của đất nước là phải xây thêm 1 số đường sao cho sau khi xây xong, 2 thành phố bất kì luôn có thể đến được với nhau.

Nhiệm vụ của bạn là phải đếm số đường tối thiểu cần xây để thỏa mãn mục tiêu của Byteland.

Input: 

  • Dòng đầu tiên chứa 2 số nguyên dương n,m là số lượng thành phố và con đường. (n<=105, m<=2*105).
  • m dòng tiếp theo, mỗi dòng gồm 2 số nguyên u,v biểu thị có 1 con đường nối giữa 2 thành phố u và v với nhau.

​Output:

  • 1 dòng duy nhất là số lượng đường tối thiểu cần xây.

Ví dụ

  • input
    4 2
    1 2
    3 4
    output
    1
Back to Top