[백준] 4195 친구 네트워크 [자바]

 

---

https://brenden.tistory.com/33

[알고리즘] 유니온 파인드 (Union-Find)

https://steady-coding.tistory.com/111

[BOJ] 백준 4195번 : 친구 네트워크 (JAVA)

 

 

---

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

public class Main {
	static int[] parent;
	static int[] level;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			int count = 0;
 			HashMap<String, Integer> hashmap = new HashMap<>();
 			int M = Integer.parseInt(br.readLine());
 			parent = new int[M*2];
 			level = new int[M*2];
 			for(int i = 0; i < M*2; i++) {
 				parent[i] = i;
 				level[i] = 1;
 			}
 			for(int i = 0; i < M; i++) {
 				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 				String str1 = st.nextToken();
 				String str2 = st.nextToken();
 				int x = 0;
 				int y = 0;
 				if(!hashmap.containsKey(str1)) {
 					hashmap.put(str1, count++);
 				}
 				x = hashmap.get(str1);
 				if(!hashmap.containsKey(str2)) {
 					hashmap.put(str2, count++);
 				}
 				y = hashmap.get(str2);
 				union(x, y);
 				int cnt = 0;
 				cnt = find(x);
 				cnt = level[cnt];
 				sb.append(cnt).append('\n');
 			}
 		}
 		System.out.println(sb);
 	}
 	static int find(int x) {
 		if(x == parent[x]) {
 			return x;
 		}
 		return parent[x] = find(parent[x]);
 	}
 	static void union(int x, int y) {
 		x = find(x);
 		y = find(y);
 		if(x != y) {
 			if(x < y) {
 				parent[y] = x;
 				level[x] = level[y] + level[x];
 			}
 			else {
 				parent[x] = y;
 				level[y] = level[x] + level[y];
 			}
 		}
 	}
 	static boolean isSameParent(int x, int y) {
 		if(parent[x] == parent[y]) {
 			return true;
 		}
 		return false;
 	}
}