题目链接：http://codeforces.com/PRoblemset/problem/766/D
题目大意：这货要建一个n个词的字典，然后里面有m组关系（相似或是对立关系），其中关系是一组（两个词）一组录入的； 每次录入的时候都要回答这个关系是不是矛盾（比如先录入了like和love是近义词，然后录入like和hate是反义词，这时候再录入love和hate是近义词就会产生矛盾）； 录入完之后，会有q组的询问，每组询问两个词，回答他们之间的关系（同义词输出1，反义词输出2，没关联输出3）。
思路：先用map把每个词都编号好，然后只需要对这n个词做个并查集就好。
开2n的数组，前半部分是本义，后半部分代表这个词的反义词的祖先。
如果第i个词和第j个词同义，那么i和j应该是同一个祖先，i+n和j+n应该同一个祖先； 如果第i个词和第j个词反义，那么i和j+n应该同一个祖先，i+n和j应该同一个祖先。
代码：
#include <iostream>#include <map>#include <string>using namespace std;int father[200005];//祖先int finding(int x)//带状态压缩的找祖先{ int fx=x; while(father[fx]!=fx) { fx=father[fx]; } while(father[x]!=x) { int t=x; x=father[x]; father[t]=fx; } return x;}void uni(int a,int b)//加入同一集合{ a=finding(a); b=finding(b); father[a]=b;}int main(){ map<string,int> mp; int n,m,q; while(cin>>n>>m>>q) { mp.clear(); for(int i=0 ; i<n ; i++) { string s; cin>>s; mp[s]=i; } for(int i=0 ; i<n ; i++) { father[i]=i; father[i+n]=i+n; } for(int i=0 ; i<m ; i++) { int t ; cin>>t; string s1,s2; cin>>s1>>s2; int a=mp[s1]; int b=mp[s2]; if(t==1)//同义 { if(finding(a)==finding(b+n)||finding(a+n)==finding(b)) { cout<<"NO"<<endl; } else { uni(a,b); uni(a+n,b+n); cout<<"YES"<<endl; } } else//反义 { if(finding(a)==finding(b)||finding(a+n)==finding(b+n)) { cout<<"NO"<<endl; } else { uni(a+n,b); uni(a,b+n); cout<<"YES"<<endl; } } } for(int i=0 ; i<q ; i++) { string s1,s2; cin>>s1>>s2; int a=mp[s1]; int b=mp[s2]; if(finding(a)==finding(b)) { cout<<1<<endl; } else if(finding(a)==finding(b+n)) { cout<<2<<endl; } else { cout<<3<<endl; } } } return 0;}新闻热点
疑难解答
