2011.计算机院.Problem D.公式推导

野性酷女 2023-07-23 11:55 2阅读 0赞

**题目描述**

数理逻辑是计算机科学中很重要的一环，而公式的自动推导就是这门科学的研究方向之一。虽然目前复杂的公式推导还难以做到，但一个简单的推导机器还是可以很容易实现的  
一个“蕴含式”可以表示为 A --> B ，意为A可以推出B，其中A和B均为非空的条件的集合（在本题中每一个条件用单独的一个小写字母表示）。比如 abc --> de 表示如果条件a、b、c均成立则可以推出d、e都成立。  
现已知有N个 推导规则。最后给出一条新的推导规则，在已知的情况，求最后一条规则是否成立

HINT对公式的读入建议使用scanf(“%s%\*s%s”,a,b)  
公式的推导基于Armstrong 公理，即满足：  
自反律：若属性集Y 包含于属性集X，属性集X 包含于U，则X–>Y 在R 上成立。  
增广律：若X –> Y 在R 上成立，且属性集Z 包含于属性集U，则XZ–>YZ 在R 上成立。  
传递律：若X –> Y 和 Y –> Z在R 上成立，则X –> Z 在R 上成立。

**输入格式**

多组数据，以EOF结束。  
每组数据的第一行为一个数N(0≤ N≤ 10000)  
之后N行每行的形式为：条件集合A+空格+“–>”+空格+条件集合B，表示A可以推出B  
集合中每一个小写字母表示一个条件（条件数不会超过26）  
之后再来一行，表示推导结果（格式同上）

**输出格式**

每组数据输出一行，YES表示可以推导出，NO表示不能

**输入样例**

2
    a --> bc
    b --> d
    a --> d
    2
    a --> b
    a --> c
    b --> c

**输出样例**

YES
    NO

只会一种情况：已知中有要推导的

#include<bits/stdc++.h>
    using namespace std;
    int main() { 
    	int n;
    	vector<string >p;
    	vector<string >q;
    	char s1[27],s2[27];
    	while(scanf("%d",&n)!=EOF) { 
    		int flag=0;
    		getchar();
    		for(int i=0; i<n; i++) { 
    			scanf("%s%*s%s",s1,s2);
    			p.push_back(s1);
    			q.push_back(s2);
    		}
    		scanf("%s%*s%s",s1,s2);
    		for(int i=0; i<p.size(); i++) { 
    			if(p[i]==s1&&q[i]==s2) { 
    				flag=1;
    				cout<<"YES\n";
    				break;
    			}
    		}
    	}
    }