[백준] 4195 - 친구 네트워크

[문제링크]

4195번: 친구 네트워크

 

0. disjoint set 문제

 

1. parents 배열 외에도, popul배열을 둬서 배열의 인구수를 관리한다.

 

2. popul배열은 서로 다른 set의 merge시에만, 흡수되는 쪽의 인구를 반대쪽에 누적시킴으로서 계산된다.

 

3. 문자열로 들어오는 사람 이름을 처리하기 위해, HashMap에 index와 함께 저장하였다.

 

4. 새로운 입력마다 두 사람의 set의 merge시도를 하며, 같은 집합일 경우 현재 인구를,

  - 다른 집합일 경우 합친 후 인구를 반환한다.

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			N = pint(br.readLine());
			HashMap<String, Integer>people=new HashMap<>();
			init();
			
			int idx=0;
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String fst = st.nextToken();
				String snd = st.nextToken();
				int fidx,sidx;
				if(people.containsKey(fst)) {
					fidx=people.get(fst);
				}else {
					people.put(fst, idx);
					fidx=idx++;
				}
				
				if(people.containsKey(snd)) {
					sidx=people.get(snd);
				}else {
					people.put(snd, idx);
					sidx=idx++;
				}
				sb.append(mergeGroup(fidx, sidx)).append("\n");
			}
			
		}System.out.println(sb);
		
	}
	static int N;
	static int[]parents;
	static int[]popul;
	
	static void init() {
		parents=new int[2*N];
		popul=new int[2*N];
		for (int i = 0; i < parents.length; i++) {
			parents[i]=i;
			popul[i]=1;
		}
	}
	
	static int getRoots(int x) {
		if(parents[x]!=x)return parents[x]=getRoots(parents[x]);
		return x;
	}
	
	static int mergeGroup(int x, int y) {
		int gx = getRoots(x), gy=getRoots(y);
		if(gx==gy)return popul[gx];
		
		parents[gy]=gx;
		popul[gx]+=popul[gy];
		return popul[gx];
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면