程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hihoCoder_#1066_無間道之並查集

hihoCoder_#1066_無間道之並查集

日期:2017/1/21 12:44:09      編輯:C++入門知識

hihoCoder_#1066_無間道之並查集


#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

 

分析:op=0,表示name1,name2是有關系的;op=1表示查詢name1,name2是否有關系。map把string轉化成int,然後並查集即可。

 

代碼清單:

 

#include
#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int maxn = 1e5 + 5; int n,op,id,idx1,idx2; string name1,name2; mapidx; int father[maxn]; int Find(int x){return x!=father[x] ? father[x]=Find(father[x]) : father[x];} void Union(int x,int y){ int xx=Find(x); int yy=Find(y); if(xx!=yy) father[xx]=yy; } int get_idx(string name){ if(idx.count(name)) return idx[name]; idx[name]=++id; return id; } void init(){ idx.clear(); for(int i=1;i<=maxn;i++) father[i]=i; id=0; } void input(){ scanf(%d,&n); } void solve(){ for(int i=0;i>op>>name1>>name2; idx1=get_idx(name1); idx2=get_idx(name2); if(op==0){ Union(idx1,idx2); } else{ if(Find(idx1)==Find(idx2)) cout<

 


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved