Đếm số hàng xóm phân biệt của đỉnh 1
Danh sách cạnh trong thực tế hay bị lặp: cùng một cặp người quen có thể được ghi lại nhiều
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
Danh sách cạnh trong thực tế hay bị lặp: cùng một cặp người quen có thể được ghi lại nhiều lần, và thứ tự hai đầu cũng có thể đảo. Nếu cứ đếm thô số dòng có liên quan tới đỉnh 1, ta sẽ đếm trùng và báo cáo sai số người quen thật sự.
Yêu cầu
Cho m cạnh vô hướng, mỗi cạnh là một cặp đỉnh. Danh sách có thể chứa cạnh lặp: cùng một cặp (u, v) có thể xuất hiện nhiều lần, và một cạnh có thể được ghi là u v hoặc v u đều như nhau. Hãy đếm số đỉnh phân biệt kề với đỉnh 1. Nếu đỉnh 1 không có cạnh nào, kết quả là 0.
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 in thêm chữ nào. 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) là một
cạnh vô hướng. Cạnh lặp được phép xuất hiện, nhưng không có khuyên.
- 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ố đỉnh phân biệt kề với đỉnh 1.
Ràng buộc
- Cạnh là vô hướng, cạnh u v và cạnh v u là một.
- Cạnh lặp phải được đếm đúng một lần.
- Mỗi bộ dữ liệu có thời gian chạy 1 giây.
Ví dụ 1
Input
5 4
1 2
1 3
3 4
1 2
Output
2
Ví dụ 2
Input
3 1
2 3
Output
0
Giải thích
Dữ liệu vào:
Đỉnh 1 xuất hiện trong cạnh 1-2 hai lần (dòng thứ nhất và dòng thứ tư) và trong cạnh 1-3 một lần, nhưng chỉ có hai hàng xóm phân biệt là 2 và 3. 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.
