題目鏈接：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;}新聞熱點
疑難解答
