In bậc của từng đỉnh
Trong đồ thị vô hướng, bậc của một đỉnh là số cạnh có đầu mút tại đỉnh đó. Bậc là số liệ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
Trong đồ thị vô hướng, bậc của một đỉnh là số cạnh có đầu mút tại đỉnh đó. Bậc là số liệu đầu tiên và đơn giản nhất để biết một đỉnh nổi bật hay hẻo lánh trong mạng lưới. Khi cộng tất cả các bậc lại, ta được đúng hai lần số cạnh.
Yêu cầu
Cho đồ thị vô hướng gồm n đỉnh đánh số 1..n và m cạnh. Hãy in ra bậc của từng đỉnh theo đúng thứ tự đỉnh 1, 2, ..., n, tất cả trên một dòng, mỗi số cách nhau đúng một dấu cách. Đỉnh không kề với cạnh nào có bậc 0 nhưng vẫn phải được in ra.
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. Đúng n số trên một dòng, cách nhau một dấu cách, 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ạnh này làm tăng bậc của cả u và v lên 1.
- Nếu m = 0 thì không có dòng cạnh nào.
Output
In ra stdout một dòng gồm đúng n số nguyên là bậc của các đỉnh 1, 2, ..., n, phân tách bằng một dấu cách. Kết thúc dòng bằng ký tự xuống dòng.
Ràng buộc
- Cạnh là vô hướng: mỗi cạnh cộng 1 vào bậc của cả hai đầu mút.
- Đồ 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
4 3
1 2
2 3
3 4
Output
1 2 2 1
Ví dụ 2
Input
3 0
Output
0 0 0
Giải thích
Dữ liệu vào:
Các cạnh là 1-2, 2-3, 3-4, nên bậc lần lượt là 1, 2, 2, 1. 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.
