给一些单词,它们可能是同义或者反义,给出一些关系定义,从前面的定义开始建立关系,如果有的关系定义和之前的冲突输出NO,否则输出YES。
然后查询q次单词x和单词y的关系。
扩展域并查集
1~n 存朋友,n+1~2n 存敌人
#include <iostream> #include <map> using namespace std ; const int N=1e6+3; int fa[N],m,K; int n; int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); } void cmb(int x,int y){ int fx=find(x),fy=find(y); fa[fy]= fx; } map<string,int> mp; signed main(){ int i,j,tes; string s1,s2; cin>>K>>n>>tes; for(i=1;i<=K;i++){ cin>>s1; mp[s1]=i; fa[i]=i; fa[i+K]=i+K; } int op; for(i=1;i<=n;i++){ cin>>op>>s1>>s2; int x=mp[s1],y=mp[s2]; int fx=find(x),fy=find(y); if(op==1){ if(fx==find(y+K)){ cout<<"NO\n";continue;} cout<<"YES\n"; cmb(x,y); cmb(find(x+K),find(y+K)); } else{ if(fx==fy) {cout<<"NO\n";continue;} cout<<"YES\n"; cmb(find(x+K),fy); cmb(find(y+K),fx); } } for(i=1;i<=tes;i++){ cin>>s1>>s2; int x=mp[s1],y=mp[s2]; if(find(x)==find(y)) cout<<1; else if(find(x)==find(y+K)) cout<<2; else cout<<3; cout<<endl; } }
标签:Dictionary,int,s2,s1,fa,mp,Mahmoud,CF766D,find From: https://www.cnblogs.com/towboa/p/17263057.html