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 tập thứ tự có là dàn (lattice)

    Cho tập thứ tự bộ phận trên n phần tử qua các cặp 'a ⪯ b' (lấy bao đóng bắc cầu, có phản xạ). Kiểm tra nó có phải là DÀN hay không: mọi cặp phần tử đều có cận trên nhỏ nhất (lub) DUY NHẤT và cận dưới lớn nhất (glb) DUY NHẤT.

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

      Dòng 1: n m. m dòng: a b nghĩa là a ⪯ b.

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

      1 ≤ n ≤ 100, 0 ≤ m ≤ n*n.

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

      YES nếu là dàn, ngược lại NO.

    Ví dụ:

    Đầu vào:

    4 4
1 2
1 3
2 4
3 4

    Đầu ra:

    YES

    Giải thích:

    Hình thoi 1<2,3<4: mọi cặp có lub & glb duy nhất → là dàn → YES.

    Đang tải editor...