华师一附中OI组

标题: P1237 冗余依赖 [打印本页]

作者: admin 时间: 2018-5-12 23:27
标题: P1237 冗余依赖
https://www.luogu.org/problemnew/show/P1237

题目描述
在设计关系数据库的表格时，术语“函数依赖”（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中，所有的依赖都是冗余的。

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

输入输出格式
输入格式：
输A的文件第一行是一个不超过100的整数n，它表示文件中函数依赖的个数。从第二行起每一行是一个函数依赖且互不重复，每行包含用字符“-”和“>”隔开的非空域列表。列表月包含大写的字母，函数依赖的数据行中不包括空格和制表符，不会出现“平凡”冗余依赖（如A->A）。虽然文件中没有对函数依赖编号，但其顺序就是编号1到n。

输出格式：
每一个冗余依赖，以及其他依赖的一个序列以说明该依赖是冗余的，先是一个FD，然后是依赖函数号，接着是"is redundant using FDs：”最后是说明的序列号。

如果许多函数依赖的序列都能被用来说明一个依赖是冗余的，则输出其中最短的证明序列。如果这些函数依赖中不包含冗余依赖，则输出“No redundant FDs”信息。

输入输出样例
输入样例#1：
【输入1】
3
A->BD
BD->C
A->C
【输入2】
6
P->RST
VRT->SQP
PS->T
Q->TR
QS->P
SR->V
输出样例#1：
【输出1】
FD 3 is redundant using FDs: 1 2
【输出2】
FD 3 is redundant using FDs: 1
FD 5 is redundant using FDs: 4 6 2
说明
1、{即C可以通过1、2得到}

欢迎光临华师一附中OI组 (http://hsyit.cn/)