BAEK_4195_친구네트워크

19 Oct 2019 in Sidemenu / BaekJoon

https://www.acmicpc.net/problem/4195

4195. 친구네트워크

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

public class Main {
	static int F, size = 200000, cnt;
	static int[] root = new int[size], rootcnt = new int[size];
	static String parent, child;
	static Map<String, Integer> map;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		for (int tc = 0, T = toInt(br.readLine()); tc < T; tc++) {
			init();
			F = toInt(br.readLine());
			for (int i = 0; i < F; i++) {
				st = new StringTokenizer(br.readLine());
				parent = st.nextToken();
				child = st.nextToken();
				sb.append(union(getIdx(parent), getIdx(child))).append("\n");
			}
		}
		System.out.println(sb);
	}

	static int getIdx(String name) {
		if (map.containsKey(name)) {
			return map.get(name);
		}
		map.put(name, cnt++);
		return map.get(name);
	}

	static int find(int n) {
		return root[n] == n ? n : (root[n] = find(root[n]));
	}

	static int union(int parent, int child) {
		int rootp = find(parent);
		int rootc = find(child);
		if (rootp != rootc) {
			root[rootc] = rootp;
			rootcnt[rootp] += rootcnt[rootc];
			rootcnt[rootc] = 1;
		}
		return rootcnt[rootp];
	}

	static void init() {
		cnt = 0;
		map = new HashMap<>();
		for (int i = 0; i < size; i++) {
			root[i] = i;
			rootcnt[i] = 1;
		}
	}

	static int toInt(String input) {
		return Integer.parseInt(input);
	}
}