OpenJudge

10:【回朔】冗余依赖

总时间限制:
1000ms
内存限制:
1024000kB
描述

在设计关系数据库的表格时,术语“函数依赖”(FD)被用来表示不同域之间的关系。函数依赖是描述一个集合中的域的值与另一个集合中的域的值之间的关系。记号x->Y被用来表示当集合X中的域被赋值后,集合Y的域就可以确定相应的值。例如,一个数据表格包含“社会治安编号”(S)、“姓名”(N)、“地址”(A)、“电话”(P)的域,并且每个人都与某个特定的互不相同的S值相对应,根据域S就可以确定域NAP的值。这就记作S->NAP

    写一个程序以找出一组依赖中所有的冗余依赖。一个依赖是冗余的是指它可以通过组里的其他依赖得到。例如,如果组里包括依赖A->BB->CA->C,那么第三个依赖是冗余的,因为域C可以用前两个依赖得到(A确定了域B的值,同样域B确定了域C的值)。在A->BB->CC->AA->CC->BB->A中,所有的依赖都是冗余的。

    现在要求你编写一个程序,从给定的依赖关系中找出冗余的。

输入
输入的文件第一行是一个不超过100的整数n,它表示文件中函数依赖的个数。从第二行起每一行是一个函数依赖且互不重复,每行包含用字符“-”和“>”隔开的非空域列表。域列表只包含大写的字母,函数依赖的数据行中不包括空格和制表符,不会出现“平凡”冗余依赖(如A->A)。虽然文件中没有对函数依赖编号,但其顺序就是编号1到n。
输出
每一个冗余依赖,以及其他依赖的一个序列以说明该依赖是冗余的,先是一个FD,然后是依赖函数号,接着是“is redundant using FDs:”最后是说明的序列号。
如果许多函数依赖的序列都能被用来说明一个依赖是冗余的,则输出其中最短的证明序
列。如果这些函数依赖中不包含冗余依赖,则输出“No redundant FDs”信息。
样例输入
 6
    P->RST
    VRT->SQP
    PS->T
    Q->TR
    QS->P
    SR->V
样例输出
 FD 3 is redundant using FDs:1
 FD 5 is redundant using FDs:4 6 2
来源
长郡双语题目
全局题号
10769
添加于
2016-11-02
提交次数
0
尝试人数
0
通过人数
0