Đếm số đỉnh cô lập
Trong một mạng lưới, phần lớn các điểm đều có đường nối tới nơi khác, nhưng vẫn có những
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 mạng lưới, phần lớn các điểm đều có đường nối tới nơi khác, nhưng vẫn có những điểm hoàn toàn tách biệt: không có một đường nào chạm tới. Những điểm như vậy gọi là đỉnh cô lập và thường là dấu hiệu của dữ liệu thiếu.
Yêu cầu
Cho đồ thị vô hướng gồm n đỉnh đánh số 1..n và m cạnh. Đỉnh cô lập là đỉnh có bậc bằng 0, tức là không có cạnh nào kề với nó. Hãy đếm xem đồ thị có bao nhiêu đỉnh như vậy.
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) mô tả
một cạnh vô hướng giữa u và v. Cả u và v đều không còn cô lập sau cạnh này.
- Nếu m = 0 thì mọi đỉnh đều cô lập và không có dòng cạnh nào.
Output
In ra stdout một số nguyên duy nhất: số đỉnh có bậc bằng 0.
Ràng buộc
- Cạnh là vô hướng: một cạnh cứu cả hai đầu mút khỏi cô lập.
- Đồ thị đơn: không có cạnh bội và không có khuyên.
- Mỗi bộ dữ liệu có thời gian chạy 1 giây.
Ví dụ 1
Input
5 3
1 2
2 3
3 4
Output
1
Ví dụ 2
Input
6 0
Output
6
Giải thích
Dữ liệu vào:
Các cạnh là 1-2, 2-3, 3-4. Bậc của các đỉnh 1..5 lần lượt là 1, 2, 2, 1, 0, nên chỉ đỉnh 5 là cô lập và 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.
