[백준 : 4195] 친구 네트워크 - 유니온 파인드

부모의 값을 크기 * -1로 유지하여 최적화 할 수 있는 Weighted Union Find를 이용하여 해결

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	public static int T;
	public static int F;
	public static Map<String, Integer> map;
	public static int parent[];

	public static int find(int x) {
		if (parent[x] < 0) {
			return x;
		}
		return parent[x] = find(parent[x]);
	}

	public static int union(int n1, int n2) {
		int p1 = find(n1);
		int p2 = find(n2);

		if (p1 == p2) {
			return parent[p1] * -1;
		}

		if (parent[p1] > parent[p2]) {
			parent[p2] += parent[p1];
			parent[p1] = p2;
			return parent[p2] * -1;
		} else {
			parent[p1] += parent[p2];
			parent[p2] = p1;
			return parent[p1] * -1;
		}

	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());

		for (int t = 0; t < T; t++) {
			F = Integer.parseInt(br.readLine());
			map = new HashMap<>();

			parent = new int[200000];
			Arrays.fill(parent, -1);

			int index = 0;
			for (int f = 0; f < F; f++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String str1 = st.nextToken();
				String str2 = st.nextToken();
				int n1, n2;
				if (map.containsKey(str1)) {
					n1 = map.get(str1);
				} else {
					n1 = index;
					map.put(str1, index++);
				}

				if (map.containsKey(str2)) {
					n2 = map.get(str2);
				} else {
					n2 = index;
					map.put(str2, index++);
				}

				System.out.println(union(n1, n2));
			}
		}

	}
}