Bậc nhỏ nhất và bậc lớn nhất của đồ thị
Hai con số mô tả nhanh một mạng lưới là bậc nhỏ nhất và bậc lớn nhất. Bậc lớn nhất cho
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
Hai con số mô tả nhanh một mạng lưới là bậc nhỏ nhất và bậc lớn nhất. Bậc lớn nhất cho biết đỉnh "đông bạn" nhất có bao nhiêu kết nối, còn bậc nhỏ nhất cho biết có đỉnh nào bị bỏ rơi hoàn toàn hay không.
Yêu cầu
Cho đồ thị vô hướng gồm n đỉnh đánh số 1..n và m cạnh. Bậc của một đỉnh là số cạnh kề với nó. Hãy in ra bậc nhỏ nhất và bậc lớn nhất trong tất cả các đỉnh, theo thứ tự đó và cách nhau đúng một dấu cách. Lưu ý là phải xét mọi đỉnh từ 1 tới n, kể cả những đỉnh không xuất hiện trong danh sách cạnh (bậc 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 hai 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.
- Nếu m = 0 thì mọi đỉnh đều có bậc 0 và không có dòng cạnh nào.
Output
In ra stdout một dòng gồm hai số nguyên min max cách nhau một dấu cách: bậc nhỏ nhất rồi bậc lớn nhất.
Ràng buộc
- Đồ thị đơn, vô hướng; đỉnh cô lập vẫn được tính với bậc 0.
- Nếu m > 0 thì bậc nhỏ nhất có thể vẫn là 0 do còn đỉnh cô lập.
- 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
Ví dụ 2
Input
3 0
Output
0 0
Giải thích
Dữ liệu vào:
Bậc của các đỉnh 1, 2, 3, 4 lần lượt là 1, 2, 2, 1, nên bậc nhỏ nhất là 1 và bậc lớn nhất là 2. 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.
