D 求XF+闭包

题目描述

如何设计一个好的数据库不仅仅是一个理论研究问题，也是一个实际应用问题。在关系数据库中不满足规范化理论的数据库设计会存在冗余、插入异常、删除异常等现象。 

     设R(U)是一个关系模式，U={ A1,A2, ……, An}。其中Ai是关系的属性，X,Y是U的子集。函数依赖 XàY 定义了数据库中属性集X与Y的依赖关系。根据Armstrong公理，函数依赖满足： 

（1）       自反律：若Ai∈X,  则 X→Ai .   特别地，Ai àAi . 

（2）       增广律：若 X→Y,  则 ZX→ZY.      (ZX 是指集合Z与X的并集 ) 

（3）       传递律：若 X→Y,  Y→Z,  则 X→Z. 

（4）       分解律：若 X→Y,  则 X→Ai        ( 若属性Ai∈Y  ) 

（5）       合并律：若 X→Y,  X→Z,  则 X→YZ. 

 已知 F 是关系模式R(U)上的函数依赖集，利用Armstrong公理系统可以推导出更多的函数依赖。设X是属性集U={ A1,A2, ……, An} 的子集， 定义X关于F的闭包XF+ 

XF+={ Ai | 若X→ Ai可以通过Armstrong公理导出} 
对于给定的U , F ,X, 请求出XF+

输入

第一行： T        表示以下有T组测试数据             （ 1≤T ≤5 ） 

对每组数据， 
      第1行： n  m  k       n 表示U中属性个数（ 1≤n≤26 ）, 用大写字母表示 
                              m表示X中属性个数（ 1≤m≤26 ） 
                              k个函数依赖  （1≤ k ≤ 20 ） 
      第2行:  字符串U      n个大写字母 

第3行:  字符串X      m个大写字母 

接下来有K行，每行有两个字符串 S T，用一个空格隔开。 表示 SàT 
 

输出

对每组测试数据，输出占一行输出XF+，要求按字母序输出。

样例输入 

1
6 2 4
ABGDCI
AD
A  B
BD  I
AG  C
C  D

样例输出 

ABDI

关于闭包的概念

截取大佬博客的讲述

完整链接 https://www.cnblogs.com/imysql/p/5487213.html

知道了闭包的概念 这个题目就非常简单了，就是一遍遍遍历

#include<iostream>
#include<set>
#include<map>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		set<char> se;//存最终结果 
		set<char>::iterator ite;
		map<string,string> ma;//对应的字符串的关系 
		map<string,string>::iterator ite1;
		map<string,int> vis;//标记该字符串是否已被加入 
		int n,m,k;
		cin>>n>>m>>k;
		string s;
		cin>>s;
		cin>>s;
		int len=s.length();
		for(int i=0;i<len;i++)
		{
			se.insert(s[i]);
		}
		while(k--)
		{
			string s1,s2;
			cin>>s1>>s2;
			ma[s1]=s2;
			vis[s1]=0;
		}
		bool flag=true;
		while(flag)
		{
			flag=false;
			for(ite1=ma.begin();ite1!=ma.end();ite1++)
			{
				string ss=ite1->first;
				if(vis[ss]==0)
				{								
					int len=ss.length();
					int i;
					for(i=0;i<len;i++)
					{
						ite=se.find(ss[i]);
						if(ite==se.end())
							break;
					}
					if(i==len)
					{	
						vis[ss]=1;					
						flag=true;
						string re=ite1->second;
						for(i=0;i<re.length();i++)
							se.insert(re[i]);                               							
					}
				}
			}
			
		}
		for(ite=se.begin();ite!=se.end();ite++)
			cout<<*ite;
		puts("");
	}
	return 0;
}