Virtual Friends

题意:问你就是到每句话的这两个人的朋友网里面有多少人

思路： 并查集

import java.util.*;
import java.io.*;

public class Main {
	int M = 100000;
	int n, m;
	HashMap<String, Integer> hm = new HashMap<String, Integer>();//用来给字符串编号
	int patten[] = new int[M + 1];
	int ans[] = new int[M + 1];

	public static void main(String[] args) {
		new Main().work();
	}

	void work() {
		Scanner sc = new Scanner(new BufferedInputStream(System.in));
		while (sc.hasNext()) {
			hm.clear();
			n = sc.nextInt();
			for (int j = 0; j < n; j++) {
				//并查集初始化
				for (int i = 1; i <=M; i++) {
					patten[i] = i;
				}
				Arrays.fill(ans, 1);
				m = sc.nextInt();
				int count = 1;
				for (int i = 0; i < m; i++) {
					String s1 = sc.next();
					String s2 = sc.next();
					if (!hm.containsKey(s1)) {
						hm.put(s1, count);
						count++;
					}
					if (!hm.containsKey(s2)) {
						hm.put(s2, count);
						count++;
					}
					union(hm.get(s1), hm.get(s2));

				}
			}
		}
	}
	//并查集合并
	void union(int a, int b) {

		int pa = find(a);
		int pb = find(b);
		if (pa == pb) {
			System.out.println(ans[pa]);
			return;
		}
		if(pa>pb){
			patten[pb]=pa;
			ans[pa]+=ans[pb];
			System.out.println(ans[pa]);
		}
		else{
			patten[pa]=pb;
			ans[pb]+=ans[pa];
			System.out.println(ans[pb]);
		}
	}
	//并查集查找
	int find(int x) {
		if(patten[x]==x)
			return x;
		int t=patten[x];
		patten[x]=find(t);//路径优化
		return patten[x];
	}
}