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ị đầy đủ và đều

    • Đồ thị đầy đủ KnK_nKn​: mọi cặp đỉnh đều có cạnh nối; mỗi đỉnh có bậc n−1n-1n−1 và số cạnh là (n2)=n(n−1)2\binom{n}{2}=\frac{n(n-1)}{2}(2n​)=2n(n−1)​.
    • Đồ thị đều (regular): mọi đỉnh có cùng một bậc.

    Cho đồ thị vô hướng đơn (không khuyên, không cạnh lặp), hãy in:

    • COMPLETE nếu đồ thị đầy đủ,
    • ngược lại REGULAR nếu đồ thị đều (mọi đỉnh cùng bậc),
    • ngược lại NEITHER.

    Lưu ý: KnK_nKn​ luôn là đồ thị đều, nên ta ưu tiên in COMPLETE trước.

    Ví dụ: tam giác K3K_3K3​ → COMPLETE.

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

      Dòng 1: nnn và mmm. mmm dòng tiếp theo: hai đỉnh 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: COMPLETE, REGULAR hoặc NEITHER.

    Ví dụ:

    Đầu vào:

    3 3
1 2
2 3
3 1

    Đầu ra:

    COMPLETE

    Giải thích:

    Mọi cặp trong 3 đỉnh đều có cạnh, $m=3=\binom{3}{2}$, bậc đều bằng 2 → COMPLETE.

    Đang tải editor...