백준 4195번 친구 네트워크 (JAVA)

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

4195번: 친구 네트워크

전형적인 유니온 파인드 문제이다. 엔테크 서비스 코딩테스트에 나왔던 유니온 파인드 문제를 제대로 풀지 못한게 아쉬워서 한번 더 풀어보았다.

 

public class BOJ_4195_친구네트워크 {
	static Function<String, Integer> stoi = Integer::parseInt;
	static int T, F;
	static int[] parent;
	static int[] rank;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = stoi.apply(br.readLine());
		for (int tc = 0; tc < T; tc++) {
			F = stoi.apply(br.readLine());
			parent = new int[F * 2];
			rank = new int[F * 2];
			for (int i = 0; i < F * 2; i++) {
				parent[i] = i;
				rank[i] = 1;
			}
			Map<String, Integer> network = new HashMap<>();
			StringTokenizer st;
			int idx = 0;
			for (int i = 0; i < F; i++) {
				st = new StringTokenizer(br.readLine());
				String f1 = st.nextToken();
				String f2 = st.nextToken();
				network.putIfAbsent(f1, idx++);
				network.putIfAbsent(f2, idx++);
				System.out.println(union(network.get(f1), network.get(f2)));

			}
		}

	}

	private static int union(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) {
			return rank[x];
		} else {
			parent[y] = x;
			rank[x] += rank[y];
		}
		return rank[x];
	}

	private static int find(int x) {
		return parent[x] = parent[x] == x ? x : find(parent[x]);
	}

}