Phát Hiện Chu Trình Trong Danh Sách (Thuật Toán Rùa và Thỏ Floyd)
Cho một danh sách liên kết gồm N nút (được đánh số thứ tự từ 0 đến N - 1). Mỗi nút i trỏ đến nút kế tiếp next[i].
Tiến độ của tôi ở bài này
Điểm đượ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: Two Pointers Fast & Slow, Modular Cycle Math.
Nội dung đề bài
Mô tả bài toán
Cho một danh sách liên kết gồm N nút (được đánh số thứ tự từ 0 đến N - 1). Mỗi nút i trỏ đến nút kế tiếp next[i].
Nếu nút cuối cùng trỏ đến NULL (biểu diễn bằng -1), danh sách không có chu trình. Nếu nút cuối trỏ về một nút pos (0 ≤ pos < N) trước đó, danh sách có chu trình bắt đầu từ pos.
Hãy xác định xem danh sách có chu trình hay không:
- Nếu có chu trình, in ra chỉ số của nút bắt đầu chu trình (pos).
- Nếu không có chu trình, in ra
-1.
Yêu cầu thuật toán đạt độ phức tạp thời gian O(N) và bộ nhớ phụ trợ O(1).
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng đầu chứa số nguyên N (1 ≤ N ≤ 105).
- Dòng thứ hai chứa N số nguyên
next[0],next[1], ...,next[N-1](-1 ≤ next[i] < N).
Output
- In ra chỉ số nút bắt đầu chu trình, hoặc
-1nếu không có chu trình.
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.
Ví dụ 1
Input
4
1 2 3 1Output
1Giải thích
Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.
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.