Chu trình Euler và thuật toán Hierholzer trên đồ thị có hướng
Hệ thống mạng máy chủ của AI Empire Academy gồm N trạm máy chủ (1 ≤ N ≤ 105) và M tuyến cáp quang một chiều (1 ≤ M ≤ 2 · 105). Đồ thị có thể có đa cạnh.
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: graph representation, in out degree, std vector.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu định lý Euler cho đồ thị có hướng: Tồn tại chu trình Euler khi và chỉ khi với mọi đỉnh, bán bậc vào bằng bán bậc ra (in_degree[u] == out_degree[u]) và tất cả các cạnh thuộc cùng một thành phần liên thông.
- Cài đặt thuật toán Hierholzer để khôi phục thứ tự các đỉnh trong chu trình trong thời gian tuyến tính O(V + E).
- Tối ưu hóa con trỏ cạnh hiện tại (
head[u]) để không duyệt lại các cạnh đã bị loại bỏ.
Mô tả bài toán
Hệ thống mạng máy chủ của AI Empire Academy gồm N trạm máy chủ (1 ≤ N ≤ 105) và M tuyến cáp quang một chiều (1 ≤ M ≤ 2 · 105). Đồ thị có thể có đa cạnh.
Robot bảo trì xuất phát từ trạm 1, cần đi tuần tra qua tất cả M tuyến cáp quang đúng một lần và quay trở về trạm 1.
Hãy tìm một chu trình Euler như vậy. Nếu không tồn tại chu trình Euler xuất phát từ trạm 1, in -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 1: Gồm 2 số nguyên N và M (1 ≤ N ≤ 105, 1 ≤ M ≤ 2 · 105).
- M dòng tiếp theo: Mỗi dòng gồm 2 số nguyên u, v (1 ≤ u, v ≤ N) thể hiện tuyến cáp một chiều từ u đến v.
Output
- Nếu tồn tại chu trình Euler: In ra trên một dòng M + 1 số nguyên là danh sách các đỉnh theo thứ tự đi qua trong chu trình (bắt đầu và kết thúc tại đỉnh 1).
- Nếu không tồn tại: In
-1.
Ràng buộc
- 1 ≤ N ≤ 105.
- 1 ≤ M ≤ 2 · 105.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
3 3
1 2
2 3
3 1Output
1 2 3 1Ví dụ 2
Input
3 2
1 2
2 3Output
-1
*Giải thích:* Bán bậc vào của đỉnh 1 là 0, bán bậc ra là 1 ($in \ne out$), không thể quay về đỉnh 1 sau khi đi hết các cạnh.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.