백준 4195 : 친구 네트워크

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

4195번: 친구 네트워크

[ 문제풀이 ]

두 친구가 같은 그래프에 속하는지를 판단해야 하기 때문에 Union-Find 알고리즘을 활용하면 해결할 수 있다.

다만, 매번 두 친구가 속한 그래프의 정점의 개수를 탐색한다면 시간 초과가 발생할 것이다. 이를 위해 rank 배열을 하나 선언하여 각 정점마다 자식의 수를 관리해주도록 한다.

두 친구를 union할때 자식의 수가 많은 친구를 부모로 두 친구를 합해준다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;

public class Main {
	
	static int F;
	static int[] parent, rank;
	static Map<String, Integer> hm;
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			parent = new int[200001];
			rank = new int[200001];
			hm = new HashMap<>();
			
			int T = Integer.parseInt(br.readLine());
			while (T-- > 0) {
				F = Integer.parseInt(br.readLine());
				for (int i = 0; i < 200001; ++i) {
					parent[i] = i;
					rank[i] = 1;
				}
				for (int i = 0, count = 1; i < F; ++i) {
					String[] str = br.readLine().split(" ");
					if (!hm.containsKey(str[0])) hm.put(str[0], count++);
					if (!hm.containsKey(str[1])) hm.put(str[1], count++);
					
					bw.write(union(hm.get(str[0]), hm.get(str[1])) + "\n");
				}
				hm.clear();
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static int getParent(int v) {
		return parent[v] == v ? v : (parent[v] = getParent(parent[v]));
	}
	
	public static int union(int a, int b) {
		a = getParent(a);
		b = getParent(b);
		
		if (a == b) return rank[a];
		
		if (rank[a] >= rank[b]) {
			parent[b] = a;
			rank[a] += rank[b];
			return rank[a];
		} else {
			parent[a] = b;
			rank[b] += rank[a];
			return rank[b];
		}
	}
}