冗余依赖

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 redund.in 输出文件 redund.out

【题目描述】

  在设计关系数据库的表格时,术语“函数依赖”(FD)被用来表示不同域之间的关系。函数依赖是描述一个集合中的域的值与另一个集合中的域的值之间的关系。记号X->Y被用来表示当集合X中的域被赋值后,集合Y的域就可以确定相应的值。例如,一个数据表格包含“社会治安编号”(S)、“姓名”(N)、“地址”(A)、“电话”(P)的域,并且每个人都与某个特定的互不相同的S值相对应,根据域S就可以确定域N、A、P的值。这就记作S->NAP。 
  写一个程序以找出一组依赖中所有的冗余依赖。一个依赖是冗余的是指它可以通过组里的其他依赖得到。例如,如果组里包括依赖A->B、B->C和A->C,那么第三个依赖是冗余的,因为域C可以用前两个依赖得到(域A确定了域B的值,同样域B确定了域C的值)。在A->B、B->C、C->A、A->C、C->B和B->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