[HiHoCoder]#1066 : 無間道之並查集

[HiHoCoder]#1066 : 無間道之並查集

描述

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

 

 

 

 

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	Map map = new HashMap<>();
	
	private String find(String str){
		if(map.get(str)==str){
			return str;
		}
		String s = find(map.get(str));
		map.put(str,s);
		return s;
	}
	
	private void init(String str){
		if(map.get(str)==null){
			map.put(str, str);
		}
	}
	
	private void insert(String a,String b){
		String fda = find(a);
		String fdb = find(b);
		if(fda.equals(fdb)) return;
		map.put(fdb, fda);
	}
	
	public static void main(String args[]){
		
/*		Scanner sc = null;
		try {
			sc = new Scanner(new FileInputStream("D:\\Desktop\\test.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}*/
		
		Scanner sc = new Scanner(System.in);
		Main main = new Main();
		int num = sc.nextInt();
		while(num-->0){
			int in = sc.nextInt();
			String a = sc.next();
			String b = sc.next();
			if(in==0){
				main.init(a);
				main.init(b);
				main.insert(a, b);
			}else{
				String s1 = main.find(a),s2=main.find(b);
				if(s1==null||s2==null||!s1.equals(s2)){
					System.out.println("no");
				}else{
					System.out.println("yes");
				}
			}
		}
		sc.close();
	}
}