題目大意：

#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

解題思路:
其實就是并查集的應用，先合并，在給你兩個點，判斷它們是否有公共祖先，這題主要就是點的處理，由于得把字符串轉化成點：
map<string,int> mm;//用map來實現字符串到數字的轉化
int tot=0;//初始為0
int trace(string str)
{
??? if (mm.count(str)) return mm[str];//找到就直接返回
??? else//找不到就++
??? {
??????? mm[str] = ++tot;
??????? return tot;
??? }
}

AC代碼：

#include<iostream> #include<string> #include<map> using namespace std; map<string,int> mm; int tot=0,father[100005]; int trace(string str) {if (mm.count(str)) return mm[str];else{mm[str] = ++tot;return tot;} } int find1(int x) {while(x!=father[x])x=father[x];return x; } void Union(int x,int y) {if(find1(x)!=find1(y))father[find1(x)]=find1(y); }int main() {int n,op,x,y;string str1,str2;while(cin>>n){for(int i=0;i<=n;i++) father[i]=i;while(n--){cin>>op>>str1>>str2;x=trace(str1),y=trace(str2);if(op) cout<<((find1(x)==find1(y))?"yes":"no")<<endl;else Union(x,y);}}return 0; }

?

轉載于:https://www.cnblogs.com/gaojupeng/p/4439489.html

總結

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

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