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] Kiểm tra đồ thị Euler

    Một đồ thị vô hướng liên thông:

    • có chu trình Euler (đi qua mỗi cạnh đúng một lần và quay về điểm xuất phát) khi và chỉ khi mọi đỉnh đều có bậc chẵn;
    • có đường đi Euler (không nhất thiết quay về) khi và chỉ khi có đúng 2 đỉnh bậc lẻ.

    Giả sử đồ thị đã liên thông. Hãy đếm số đỉnh bậc lẻ và in:

    • EULER nếu có chu trình Euler (0 đỉnh bậc lẻ),
    • SEMI nếu chỉ có đường đi Euler (đúng 2 đỉnh bậc lẻ),
    • NONE nếu không có (số đỉnh bậc lẻ khác 0 và khác 2).

    Ví dụ: tam giác có 0 đỉnh bậc lẻ → EULER.

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

      Dòng 1: nnn và mmm. mmm dòng tiếp theo: hai đỉnh u,vu, vu,v của mỗi cạnh.

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

      1≤n≤1051 \le n \le 10^51≤n≤105, 0≤m≤2⋅1050 \le m \le 2\cdot10^50≤m≤2⋅105.

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

      Một dòng: EULER, SEMI hoặc NONE.

    Ví dụ:

    Đầu vào:

    3 3
1 2
2 3
3 1

    Đầu ra:

    EULER

    Giải thích:

    Mọi đỉnh bậc 2 (chẵn) → 0 đỉnh bậc lẻ → có chu trình Euler → EULER.

    Đang tải editor...