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 phản xạ, đối xứng, bắc cầu

    Cho quan hệ hai ngôi RRR trên tập {1,…,n}\{1,\ldots,n\}{1,…,n} biểu diễn bằng ma trận MMM (Mij=1M_{ij}=1Mij​=1 nếu i R ji\,R\,jiRj). Hãy kiểm tra ba tính chất:

    • Phản xạ (reflexive): ∀i, i R i\forall i,\ i\,R\,i∀i, iRi (tức Mii=1M_{ii}=1Mii​=1).
    • Đối xứng (symmetric): ∀i,j, i R j⇒j R i\forall i,j,\ i\,R\,j \Rightarrow j\,R\,i∀i,j, iRj⇒jRi.
    • Bắc cầu (transitive): ∀i,j,k, (i R j∧j R k)⇒i R k\forall i,j,k,\ (i\,R\,j \wedge j\,R\,k) \Rightarrow i\,R\,k∀i,j,k, (iRj∧jRk)⇒iRk.

    In ba số 0/10/10/1 tương ứng phản xạ, đối xứng, bắc cầu.

    Ví dụ: ma trận đơn vị (chỉ đường chéo bằng 1) có cả ba tính chất → 1 1 1.

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

      Dòng 1: nnn. nnn dòng tiếp theo: mỗi dòng nnn số (0/10/10/1) — một hàng của ma trận quan hệ.

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

      1≤n≤2001 \le n \le 2001≤n≤200.

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

      Một dòng: ba số 0/10/10/1 — phản xạ, đối xứng, bắc cầu.

    Ví dụ:

    Đầu vào:

    2
1 0
0 1

    Đầu ra:

    1 1 1

    Giải thích:

    Đường chéo đều 1 → phản xạ; ma trận đối xứng; không vi phạm bắc cầu → 1 1 1.

    Đang tải editor...