#1066 : 無間道之并查集
時間限制:20000ms
單點時限:1000ms
內存限制:256MB
描述
這天天氣晴朗、陽光明媚、鳥語花香，空氣中彌漫著春天的氣息……額，說遠了，總之，小Hi和小Ho決定趁著這朗朗春光出去玩。

但是剛剛離開居住的賓館不久，抄近道不小心走入了一條偏僻小道的小Hi和小Ho就發現自己的前方走來了幾個彪形大漢，定睛一看還都是地地道道的黑人兄弟！小Hi和小Ho這下就慌了神，撿肥皂事小，這一身百把來斤別一不小心葬身他鄉可就沒處說去了。

就在兩人正舉足無措之時，為首的黑叔叔從懷里掏出了一件東西——兩張花花綠綠的紙，分別遞給了小Hi和小Ho。

小Hi和小Ho接過來，只見上面寫道（譯為中文）：“本地最大的幫派——青龍幫，誠邀您的加入！”下面還詳細的列出了加入青龍幫的種種好處。

于是兩人略感心安，在同黑叔叔們交談一番之后，已是均感相見恨晚。同時，在小Hi和小Ho表示自己不日便將回國之后，黑叔叔們也沒有再提加入幫派之事，但是那為首的黑叔叔思索一會，開口道（譯為中文）：“我現在有一個難題，思索了很久也沒法子解決，既然你們倆都是高材生，不如來幫我看看。”

小Hi和小Ho點了點頭表示沒問題，于是黑叔叔繼續說道：“這個問題是這樣的，我們幫派最近混進了許多警察的臥底，但是在我們的調查過程中只能夠知道諸如‘某人和另一個人是同陣營的’這樣的信息，雖然沒有辦法知道他們具體是哪個陣營的，但是這樣的信息也是很重要的，因為我們經常會想要知道某兩個人究竟是不是同一陣營的。”

小Hi和小Ho贊同的點了點頭，畢竟無間道也都是他們看過的。

黑叔叔接著說道：“于是現在問題就來了，我希望你們能寫出這樣一個程序，我會有兩種操作，一種是告訴它哪兩個人是同一陣營的，而另一種是詢問某兩個人是不是同一陣營的……既然你們就要回國了，不如現在就去我們幫派的總部寫好這個程序再走把。”

為了生命安全與……小Hi和小Ho都不得不解決這個問題！那么他們究竟從何下手呢？

提示：說起來其實就是不斷的合并集合嘛~
輸入
每個測試點（輸入文件）有且僅有一組測試數據。

每組測試數據的第1行為一個整數N，表示黑叔叔總共進行的操作次數。

每組測試數據的第2~N+1行，每行分別描述黑叔叔的一次操作，其中第i+1行為一個整數op_i和兩個由大小寫字母組成的字符串Name1_i, Name2_i，其中op_i只可能為0或1，當op_i=0時，表示黑叔叔判定Name1_i和Name2_i是同一陣營的，當op_i=1時，表示黑叔叔希望知道Name1_i和Name2_i是否為同一陣營的。

對于100%的數據，滿足N<=10^5, 且數據中所有涉及的人物中不存在兩個名字相同的人（即姓名唯一的確定了一個人），對于所有的i，滿足Name1_i和Name2_i是不同的兩個人。

輸出
對于每組測試數據，對于黑叔叔每次op_i=1的操作，輸出一行，表示查詢的結果：如果根據已知信息（即這次操作之前的所有op_i=0的操作），可以判定詢問中的兩個人是同一陣營的，則輸出yes，否則輸出no。

樣例輸入
10
0 Steven David
0 Lcch Dzx
1 Lcch Dzx
1 David Dzx
0 Lcch David
0 Frank Dzx
1 Steven Dzx
1 Frank David
0 Steven Dzx
0 Dzx Frank
樣例輸出
yes
no
yes
yes
/*
做這題因為我覺得他簡單，
然后看到是名字，和平常寫的是數字不一樣，就有點亂，一開始就一直想用二維vector或mulitmap來建立關系，但是大晚上的思緒很是混亂，沒有成功，就想著暴力一發，TEL,然后睡覺去了，
睡在床上就冷靜下來，頭腦清醒了，我只要把名字換成編號不就很平常一樣了嗎，再想想如何給他們編號，編號和名字一一對應，所以我就想到用map了，因為map的key值唯一，用key判斷名字是否出現，沒有出現過的名字就給他一個編號，nice！然后我安穩的碎覺了。第二天早上，早簽到，晨跑，買早餐，吃早餐，去上課前在寢室打開電腦就很快就寫出來了，AC！！開心上課去~~
*/
AC_code:

#include <bits/stdc++.h> const int MAXN = 1e5+5; using namespace std; map<string,int>mp; int k,pre[MAXN]; void getNum(string s1,string s2) {if(!mp[s1]){mp[s1] = ++k;}if(!mp[s2]){mp[s2] = ++k;} } int find(int x) {if(pre[x]==0)return x;return pre[x] = find(pre[x]); } void merge(int x,int y) {int fx = find(x),fy = find(y);if(fx != fy){pre[fx] = fy;} } int main() {int n;cin>>n;int op;string s1,s2;for(int i = 0; i < n; i++){cin>>op>>s1>>s2;getNum(s1,s2); if(op == 0){merge(mp[s1],mp[s2]);}else{int x = find(mp[s1]), y = find(mp[s2]);if(x == y)cout<<"yes"<<endl;elsecout<<"no"<<endl;}s1.clear();s2.clear();}return 0; }

下面是昨晚，我腦洞大開的暴力代碼，TEL：

#include <bits/stdc++.h> #define fFind string::npos using namespace std; int main() {int n,op,k;cin>>n;vector<string>data;string s1,s2,s3;k = 0;s3 = "00";data.push_back(s3);int flag ,temp;for(int i = 0; i < n; i++){cin>>op>>s1>>s2;if(op == 0){flag = 1;for(int j = 0; j < data.size(); j++){string st = s1 + "00" + s2;if(data[j].find(s1)!=fFind||data[j].find(s2)!=fFind){if(flag){data[j] += st;flag = 0;temp = j;}else{data[temp] += data[j];data.erase(data.begin()+j);}}else{data.push_back(st);}}}else{int flag2 = 0;for(int p = 0; p < data.size(); p++){if(data[p].find(s1)!=fFind&&data[p].find(s2)!=fFind){cout<<"yes"<<endl;flag2 = 1;break;}}if(!flag2) cout<<"no"<<endl;}}return 0; }

總結

以上是生活随笔為你收集整理的#1066 : 无间道之并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。