這天天氣晴朗、陽光明媚、鳥語花香,空氣中彌漫著春天的氣息……額,說遠了,總之,小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