[백준] 친구 네트워크(4195)

문제

[백준] 친구 네트워크(4195)

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

해설

Map을 사용해 사용자 아이디에 번호를 부여하고, union-find로 풀이하였다.

풀이

import java.util.*;
import java.io.*;

public class Main {
	static int tc, f, max;
	static Map<String, Integer> map;
	static int[] parent, count;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		tc = Integer.parseInt(br.readLine());

		while (tc-- > 0) {
			f = Integer.parseInt(br.readLine());
			max = f * 2;
			parent = new int[max];
			count = new int[max];
			map = new HashMap<>();

			int index = 0;

			for (int i = 0; i < parent.length; i++) {
				parent[i] = i;
				count[i] = 1;
			}

			for (int i = 0; i < f; i++) {
				st = new StringTokenizer(br.readLine(), " ");

				String a = st.nextToken();
				String b = st.nextToken();

				if (!map.containsKey(a))
					map.put(a, index++);
				if (!map.containsKey(b))
					map.put(b, index++);

				sb.append(union(map.get(a), map.get(b))).append("\n");
			}
		}
		
		System.out.println(sb.toString());
	}

	public static int union(int a, int b) {
		int findA = find(a);
		int findB = find(b);

		if (findA == findB)
			return count[findA];

		if (findA < findB) {
			parent[findB] = findA;
			count[findA] += count[findB];
			return count[findA];
		} else {
			parent[findA] = findB;
			count[findB] += count[findA];
			return count[findB];
		}
	}

	public static int find(int n) {
		if (parent[n] == n)
			return n;

		return parent[n] = find(parent[n]);
	}
}