Các lượt nộp

Danh sách bài

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 $R$ trên tập $\{1,\ldots,n\}$ biểu diễn bằng ma trận $M$ ( $M_{ij}=1$ nếu $i\,R\,j$ ). Hãy kiểm tra ba tính chất:

Phản xạ (reflexive): $\forall i,\ i\,R\,i$ (tức $M_{ii}=1$ ).
Đối xứng (symmetric): $\forall i,j,\ i\,R\,j \Rightarrow j\,R\,i$ .
Bắc cầu (transitive): $\forall i,j,k,\ (i\,R\,j \wedge j\,R\,k) \Rightarrow i\,R\,k$ .

In ba số $0/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: $n$ . $n$ dòng tiếp theo: mỗi dòng $n$ số ( $0/1$ ) — một hàng của ma trận quan hệ.
Ràng buộc đầu vào:
$1 \le n \le 200$ .
Định dạng đầu ra:
Một dòng: ba số $0/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...