Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán rời rạc] Xây dựng chu trình Euler (Hierholzer)

    Cho đồ thị vô hướng có chu trình Euler (liên thông, mọi đỉnh bậc chẵn). Thuật toán Hierholzer xây chu trình Euler trong thời gian tuyến tính. Để đầu ra xác định, mỗi bước ta luôn chọn đỉnh kề nhỏ nhất còn cạnh chưa dùng, bắt đầu từ đỉnh 1.

    Hãy in dãy đỉnh của chu trình Euler (có m+1 đỉnh, bắt đầu và kết thúc tại đỉnh 1).

    • Định dạng đầu vào:

      Dòng đầu n m. m dòng cạnh vô hướng u v. Bảo đảm đồ thị có chu trình Euler và đỉnh 1 có bậc > 0.

    • Ràng buộc đầu vào:

      1 <= n <= 1000; 1 <= m <= 5000.

    • Định dạng đầu ra:

      Một dòng gồm m+1 số: dãy đỉnh của chu trình Euler.

    Ví dụ:

    Đầu vào:

    3 3
1 2
2 3
3 1

    Đầu ra:

    1 2 3 1

    Giải thích:

    Chu trình Euler bắt đầu từ 1, chọn đỉnh kề nhỏ nhất: 1 2 3 1.

    Đang tải editor...