题目描述

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

     设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

原理很简单，先创建book数组用来标记已经在XF+中的字母，

如果s中的字符如果全部都在XF+中，并且t中的字母仍有不在XF+中的，则将其加入到XF+中也就是在book数组中进行标记

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
using namespace std;
int main()
{
	int t,n,m,k;
	cin>>t;
	while(t--){
	    cin>>n>>m>>k;
	    char nstr[n],mstr[m],sstr[k][26],tstr[k][26];
	    int book[26]={0};  //用来标记对应的字母是否在Xf+中，为一说明在，为0说明不在
		cin>>nstr>>mstr;
	    for(int i=0;i<k;i++){
	    	cin>>sstr[i]>>tstr[i];
	    }
	    for(int i=0;i<m;i++){  //首先将字符串mstr中的字符存放到BOOK数组中
	    	book[mstr[i]-'A']=1;
	    }
	    while(true){
	    	int bj1=0;
	    	for(int i=0;i<k;i++){  //将这k对字符依次比较
	    		int num1=0,num2=0;
	    		for(int j=0;j<strlen(sstr[i]);j++){
	    			if(book[sstr[i][j]-'A']==0)num1=-1;
	    		}
	    		for(int j=0;j<strlen(tstr[i]);j++){
	    			if(book[tstr[i][j]-'A']==0)num2=-1;
	    		}
	    		if(num1==0&&num2==-1){  //若s字符串中所有字符都在xf+中，且t字符串中有字符未在xf+中，则更新book数组
	    			for(int j=0;j<strlen(tstr[i]);j++){
	    			    book[tstr[i][j]-'A']=1;
	    		    }
	    			bj1=1;
	    		}
	    	}
	    	if(bj1==0)break;//若将k对字符串比较后，book数组未发生变化，就说明xf+已经完全求出
	    }
	    for(int i=0;i<26;i++){
	    	if(book[i]!=0)printf("%c",65+i);
	    }
	    cout<<endl;
	}
	return 0;
}