[Java] 백준 / 친구 네트워크 / 4195

[Java] 백준 / 친구 네트워크 / 4195

문제

친구 네트워크 문제 링크

접근 방식

1. Map 을 통해 새로 입력 받은 친구의 이름과 해당 인덱스를 key value로 저장한다
2. level 배열을 만들고 해당 배열에 자신을 포함하여 연결되어있는 친구 수를 저장한다 (초기화 1)
3. 유니온 파인드를 구현하고 유니온 도중에 두 친구의 최상 부모 둘의 친구 수를 합하여 한 쪽에 저장한다 ( 부모가 되는 쪽 )

코드

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

public class Main_4195 {

	
	static Map<String, Integer> map;
	static int[] parents;
	static int[] level;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		 
		
		
		for(int i=0;i<T;i++) {
			int F = Integer.parseInt(br.readLine());
			map = new HashMap<>();
			parents = new int[F * 2];
			level = new int[F * 2];
			
			for(int j=0;j<F*2;j++) {
				parents[j] = j;
				level[j] = 1;
			}
			
			int idx = 0;
			for(int j=0;j<F;j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String a = st.nextToken();
				String b = st.nextToken();
				
				
				if(!map.containsKey(a)) {
					map.put(a, idx++);
				}
				if(!map.containsKey(b)) {
					map.put(b, idx++);
				}
				
				sb.append(union(map.get(a),map.get(b))+"\n");
			}
		}
		System.out.print(sb);
		
	}
	
	
	public static int findSet(int a) {
		if(a == parents[a]) return a;
		return parents[a] = findSet(parents[a]);
	}
	
	public static int union(int a, int b) {
		
		a = findSet(a);
		b = findSet(b);
		
		if(a != b) {
			parents[b] = a;
			level[a] += level[b];
			
			level[b] = 1;
		}
		
		return level[a];
	}

}