Đếm số thành phần liên thông (đồ thị)
Xem dạng PDF
Gửi bài giải
Điểm:
2,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Cho đồ thị vô hướng G = (V, E) được biểu diễn dưới dạng danh sách cạnh. Hãy đếm số thành phần liên thông cúa đồ thị.
Đầu vào: Dòng đầu tiên là 2 số n và m, tương ứng với số lượng đỉnh, cạnh của đồ thị. Các đỉnh của đô thị được đánh số từ 1 tới n; m dòng tiếp theo mỗi dòng chứa đỉnh u, v (u != v) tương ứng với một cạnh của đồ thị.
Ràng buộc: 1<=n<=1000; 1<=m<=n*(n-1)/2;
Đầu ra: In ra số thành phần liên thông của đồ thị
Input 01:
5 4
4 1
2 1
3 2
4 3
Output 01:
2
Input 02:
5 2
4 1
2 1
Output 02:
3
Bình luận