1089 - 关系推断
给你一些已经确定的元素之间的关系，请你判断是否能从这些元素关系中推断出其他的元素关系。
题目输入
输入的第一行是一个整数N，表示测试数据的组数。
每组输入首先是一个正整数m（m<=100），表示给定元素关系的个数。
接下来m行，每行一个元素关系，格式为：
元素1<元素2 或者 元素1>元素2
元素用一个大写字母表示，输入中不会包含冲突的关系。
题目输出
对于每组输入，第一行输出“Case d:”，d是测试数据的序号，从1开始。
接下来输出所有推断出的新的元素关系，按照字典序从小到大排序，格式为：
元素1<元素2
每个元素关系占一行，输入中给定的元素关系不要输出。
如果没有新的元素关系推断出来，则输出NONE。
输入/输出样例
题目输入
2 3 A<B C>B C<D 2 A<B C<D
题目输出
Case 1: A<C A<D B<D Case 2: NONE
C语言解答
#include<stdio.h> #include<string.h> int g[26][26],flag[26][26]; void floyd() { int i,j,k; for(k=0;k<26;k++) for(i=0;i<26;i++) for(j=0;j<26;j++) if(flag[i][k]&&flag[k][j]) flag[i][j]=1; } int main() { int n,m,i,j,x,y,c=0,bj; char s[4]; scanf("%d",&n); while(n--) { memset(g,0,sizeof(g)); memset(flag,0,sizeof(flag)); scanf("%d",&m); while(m--) { scanf("%s",s); x=s[0]-'A'; y=s[2]-'A'; if(s[1]=='<') { g[x][y]=1; flag[x][y]=1; } else { g[y][x]=1; flag[y][x]=1; } } floyd(); printf("Case %d:\n",++c); for(bj=i=0;i<26;i++) for(j=0;j<26;j++) if(!g[i][j]&&flag[i][j]) { bj=1; printf("%c<%c\n",i+'A',j+'A'); } if(!bj) printf("NONE\n"); } return 0; }
C++解答
#include<stdio.h> #include<string.h> int g[26][26],flag[26][26]; void floyd() { int i,j,k; for(k=0;k<26;k++) for(i=0;i<26;i++) for(j=0;j<26;j++) if(flag[i][k]&&flag[k][j]) flag[i][j]=1; } int main() { int n,m,i,j,x,y,c=0,bj; char s[4]; scanf("%d",&n); while(n--) { memset(g,0,sizeof(g)); memset(flag,0,sizeof(flag)); scanf("%d",&m); while(m--) { scanf("%s",s); x=s[0]-'A'; y=s[2]-'A'; if(s[1]=='<') { g[x][y]=1; flag[x][y]=1; } else { g[y][x]=1; flag[y][x]=1; } } floyd(); printf("Case %d:\n",++c); for(bj=i=0;i<26;i++) for(j=0;j<26;j++) if(!g[i][j]&&flag[i][j]) { bj=1; printf("%c<%c\n",i+'A',j+'A'); } if(!bj) printf("NONE\n"); } return 0; }