Kiểm tra một dãy đỉnh có phải đường đi hợp lệ
Khi đã có đồ thị và một dãy đỉnh do ai đó đưa ra, việc đầu tiên cần làm là kiểm tra xem dãy
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
Khi đã có đồ thị và một dãy đỉnh do ai đó đưa ra, việc đầu tiên cần làm là kiểm tra xem dãy đó có thực sự là một đường đi không: hai đỉnh liên tiếp trong dãy phải được nối bằng một cạnh. Chỉ cần một mắt xích bị thiếu là cả dãy không hợp lệ.
Yêu cầu
Cho đồ thị vô hướng đơn gồm n đỉnh đánh số 1..n và m cạnh, cùng một dãy gồm k đỉnh v[1], v[2], ..., v[k] (k >= 1). Dãy được gọi là hợp lệ nếu với mọi i từ 1 tới k - 1 thì (v[i], v[i+1]) là một cạnh của đồ thị. Dãy có thể lặp lại đỉnh, miễn là mọi cặp liên tiếp đều là cạnh. Đặc biệt k = 1 luôn hợp lệ. Hãy in YES nếu hợp lệ, NO nếu khô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 YES hoặc NO bằng chữ in hoa, không in thêm gì khác. 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 có nhiều nhất một cạnh.
- Dòng tiếp theo: số nguyên k (1 <= k <= 8) là độ dài dãy.
- Dòng cuối cùng: k số nguyên v[1], v[2], ..., v[k] cách nhau bởi dấu cách, mỗi số nằm
trong khoảng 1..n.
Output
In ra stdout duy nhất một từ: YES nếu dãy hợp lệ, NO nếu tồn tại cặp liên tiếp không phải là cạnh.
Ràng buộc
- Cạnh là vô hướng: (u, v) và (v, u) cùng là một cạnh, nên dãy đi ngược chiều vẫn hợp lệ.
- Dãy được phép lặp lại đỉnh; bài toán không yêu cầu các đỉnh phải phân biệt.
- 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
4
1 2 3 4
Output
YES
Ví dụ 2
Input
4 3
1 2
2 3
3 4
4
1 3 2 4
Output
NO
Giải thích
Dữ liệu vào:
Các cặp liên tiếp (1,2), (2,3), (3,4) đều là cạnh, nên kết quả là:
Với dãy 1 3 2 4 thì cặp đầu tiên (1,3) không phải là cạnh, nên kết quả là NO.
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.
