Đế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

Hãy đọc nội quy trước khi bình luận.


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