Xây cầu
View as PDF
Submit solution
Points:
100.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Tại quần đảo ZXY có N hòn đảo, một số hòn đảo đã có cầu nối với nhau. Từ đảo này ta có thể đi sang đảo khác bằng đường đi trực tiếp hoặc đi gián tiếp qua các đảo khác. Để thuận tiện cho các phương tiện đi lại, ban quản lý sẽ xây thêm một số cầu để từ một đảo ta có thể đi đến các đảo còn lại trong quần đảo. Hãy cho biết, ban quản lý cần xây ít nhất bao nhiêu cầu?
Dữ liệu vào:
• Dòng 1: Ghi số nguyên N và M (M, N ≤ 3000). • M dòng tiếp theo, mỗi dòng ghi số nguyên dương u và v thể hiện có đường đi giữa hai đỉnh u và v (u, v ≤ N).
Kết quả: Ghi ra số cầu ít nhất cần xây thêm.
Ví dụ: 
INPUT
12 7
1 2
2 5
2 6
6 10
3 4
9 11
9 12
OUTPUT
4
Comments
c-cx manh