偏序关系

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

给定有限集上二元关系的关系矩阵，确定这个关系是否是偏序关系。

Input

多组测试数据，对于每组测试数据，第1行输入正整数n（1 <= n <= 100），第2行至第n+1行输入n行n列的关系矩阵。

Output

对于每组测试数据，若为偏序关系，则输出yes，反之，则输出no。

Sample Input

4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
4
1 0 0 1
0 1 0 0
0 0 1 0
1 0 0 1

Sample Output

yes
no

Hint

偏序关系形式定义：设R是集合A上的一个二元关系，若R满足自反性、反对称性、传递性，则称R为A上的偏序关系。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int a[105][105];
int main()
{int n, i, j, flag, k;while(~scanf("%d", &n)){for(i = 1; i <= n; i++){for(j = 1; j <= n; j++){scanf("%d", &a[i][j]);}}flag = 1;for(i = 1; i <= n; i++){///自反性，对角线全为 1if(a[i][i] != 1)flag = 0;}for(i = 1; i <= n; i++){for(j = 1; j <= n; j++){if(a[i][j] == 1 && a[j][i] == 1 && i != j){///反对称性，若 iRj && jRi，则 i = j 不成立则不具有反对称性flag = 0;}if(a[i][j] == 1){///对称性，若 iRj && jRk 则 iRk， 不成立则不具有反对称性for(k = 1; k <= n; k++){if(a[j][k] == 1 && a[i][k] != 1){flag = 0;}}}}}if(flag)  printf("yes\n");else  printf("no\n");}return 0;
}