题意:
给一些蕴含式和一个为真的语句集合,求总共能推导出的语句集合。
分析:
维护一个里面语句都为真的集合就好。ps,这水题居然只有一百多人做出来。。
代码:
//poj 1628
//sep9
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
set<char> s1[256],s2[256],s;
set<char>::iterator iter;bool f(char c){if((c<='z'&&c>='a')||(c<='Z'&&c>='A'))return true;return false;
}void print(set<char> s)
{for(char i='a';i<='z';++i)if(s.count(i)>0)printf("%c",i);for(char i='A';i<='Z';++i)if(s.count(i)>0)printf("%c",i);printf("\n");
}void scan(set<char> &s)
{s.clear();char ch;while((ch=getchar())&&!f(ch));s.insert(ch); while((ch=getchar())&&f(ch)){if(s.count(ch)==0)s.insert(ch);}
}bool subset_of_s(int i){for(iter=s1[i].begin();iter!=s1[i].end();++iter){if(s.count(*iter)==0)return false;}return true;
}int main()
{int i,m,n;scanf("%d%d",&m,&n);for(i=0;i<m;++i){scan(s1[i]); scan(s2[i]);}while(n--){scan(s);bool update;while(1){update=false;for(i=0;i<m;++i)if(subset_of_s(i)) for(iter=s2[i].begin();iter!=s2[i].end();++iter)if(s.count(*iter)==0){s.insert(*iter);update=true;}if(update==false)break;} print(s); }return 0;
}