Đếm số thành phần liên thông
Trong một lớp học, tình bạn được ghi lại bằng các cặp học sinh chơi với nhau. Tình bạn có
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Trong một lớp học, tình bạn được ghi lại bằng các cặp học sinh chơi với nhau. Tình bạn có tính hai chiều. Các nhóm bạn tách rời nhau tạo thành những "nhóm bạn thân" không ai quen ai ở nhóm khác. Hỏi cả lớp có bao nhiêu nhóm như vậy.
Yêu cầu
Cho đồ thị vô hướng gồm n đỉnh (đánh số 1..n) và m cạnh. Hãy đếm số thành phần liên thông của đồ thị, tức là số tập đỉnh lớn nhất sao cho hai đỉnh bất kỳ trong cùng một tập luôn có đường đi tới nhau và không có cạnh nào nối hai tập khác nhau. Một đỉnh không có cạnh nào cũng là một thành phần liên thông.
Quy ước nộp bài
Nộp tệp solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Chỉ in đúng một số nguyên, không thêm chữ hay dấu cách. Chỉ dùng thư viện chuẩn C++17.
Input
- Dòng đầu tiên: hai số nguyên n, m (1 <= n <= 8, 0 <= m <= 12).
- m dòng tiếp theo: mỗi dòng hai số nguyên u, v (1 <= u, v <= n, u != v) mô tả
một cạnh vô hướng giữa u và v. Giữa hai đỉnh bất kỳ có nhiều nhất một cạnh.
- Nếu m = 0 thì không có dòng cạnh nào.
Output
In ra stdout một số nguyên duy nhất: số thành phần liên thông của đồ thị.
Ràng buộc
- Cạnh là vô hướng và có thể không liên thông.
- Một đỉnh cô lập cũng được đếm là một thành phần.
- Mỗi bộ dữ liệu có thời gian chạy 1 giây.
Ví dụ 1
Input
5 3
1 2
3 4
4 5
Output
2
Ví dụ 2
Input
1 0
Output
1
Giải thích
Dữ liệu vào:
Các cạnh là 1-2, 3-4 và 4-5. Ta được nhóm {1, 2} và nhóm {3, 4, 5}; ở dữ liệu này không có đỉnh nào đứng riêng lẻ. Vậy kết quả là:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
