題目鏈接：http://codeforces.com/PRoblemset/problem/766/D
題目大意：這貨要建一個(gè)n個(gè)詞的字典，然后里面有m組關(guān)系（相似或是對(duì)立關(guān)系），其中關(guān)系是一組（兩個(gè)詞）一組錄入的； 每次錄入的時(shí)候都要回答這個(gè)關(guān)系是不是矛盾（比如先錄入了like和love是近義詞，然后錄入like和hate是反義詞，這時(shí)候再錄入love和hate是近義詞就會(huì)產(chǎn)生矛盾）； 錄入完之后，會(huì)有q組的詢(xún)問(wèn)，每組詢(xún)問(wèn)兩個(gè)詞，回答他們之間的關(guān)系（同義詞輸出1，反義詞輸出2，沒(méi)關(guān)聯(lián)輸出3）。
思路：先用map把每個(gè)詞都編號(hào)好，然后只需要對(duì)這n個(gè)詞做個(gè)并查集就好。
開(kāi)2n的數(shù)組，前半部分是本義，后半部分代表這個(gè)詞的反義詞的祖先。
如果第i個(gè)詞和第j個(gè)詞同義，那么i和j應(yīng)該是同一個(gè)祖先，i+n和j+n應(yīng)該同一個(gè)祖先； 如果第i個(gè)詞和第j個(gè)詞反義，那么i和j+n應(yīng)該同一個(gè)祖先，i+n和j應(yīng)該同一個(gè)祖先。
代碼：
#include <iostream>#include <map>#include <string>using namespace std;int father[200005];//祖先int finding(int x)//帶狀態(tài)壓縮的找祖先{ 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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
