logo AlgoBeat OnlineJudge
登录 注册

#101871. [BZOJ 1871] [Beijing2009 WinterCamp]函数依赖

内存限制:64 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

是一个属性集 上的关系模式, 的子集。若对于 的任意一个可能的关系 中不可能存在两个元组在 上的属性值相等,而在 上的属性值不等,则称“ 函数确定 ”或“ 函数依赖于 ”,记作 。其中 称为这个函数依赖的决定属性集(Determinant)。

解释:如果有函数依赖 ,当我们知道 的时候,也就知道了 ,也就是 能推出 。另外,可以简单的证明,如果 ,那么可以得到

若关系中的某一属性组的值能唯一的表示一个元组,则称该属性组为超码。若关系中的某一属性组的值能唯一地表示一个元组,而其真子集不行,则称该属性组为候选码。

解释:设有属性集合 和函数依赖 ,显然,在已知 的情况下,我们能够通过函数依赖得到整个集合的所有属性 ,那么我们称 为超码。当超码的任何一个子集都不是超码的时候,我们称之为候选码。例如 是一个超码,但是不是一个候选码,因为 的子集,它也是超码。 现在给出属性集合和函数依赖集合 ,请找出该 的候选码。

输入格式

输入文件的第一行为一个整数 ,表示属性集中的属性个数和函数依赖集中的依赖个数。这里我们默认大写字母中的前 个字母为我们所考虑的属性。接下来的 行每行一个字符串表示一个函数依赖,如 AB->DE。(中间的蕴含符号是由减号和大于号组成。另外需要说明的是,只有当我们同时得到 的时候,才能推出 )。

输出格式

第一行输出你找到的候选码的个数

接下来的 行每行输出一个候选码。候选码本身按字母顺序排列,所有候选码按照字典顺序排列输出。如果没有找到候选码,输出 No candidate key

样例

样例

样例输入 #1

5 5
AB->C
AC->B
AD->E
BC->D
E->A

样例输出 #1

4
AB
AC
BE
CE

数据范围与提示

对于 的测试数据,保证只有二元联系(即不存在函数依赖左边或右边的属性个数超过 个)。

对于 的测试数据,保证

对于 的测试数据,保证

对于 的测试数据,保证

Beijing2009 WinterCamp Day1