[BOJ] 4195. 친구 네트워크 - UnionFind

[BOJ] 4195. 친구 네트워크 - UnionFind

제출일 : 2019-11-03

문제 풀이 시간 : 2H

난이도 : ★★★☆

Problem

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

입력

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

출력

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

Example

input

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

output

2
3
4
2
2
4

Solution & Inpression

Union-Find를 활용한 문제

Code

언어 : JAVA

메모리 : 105,164 kb

실행시간 : 1500 ms

import java.io.FileInputStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt(); // 테스트 케이스의 개수 T

        for (int tc = 1; tc <= T; tc++) {

            int F = sc.nextInt();// 친구 관계 수 F <= 100,000
            makeSet(2 * F);
            map = new HashMap<>();

            for (int i = 0; i < F; i++) {
                String id1 = sc.next();
                String id2 = sc.next();

                if (!map.containsKey(id1))
                    map.put(id1, map.size());
                if (!map.containsKey(id2))
                    map.put(id2, map.size());

                System.out.println(union(map.get(id1), map.get(id2)));
            }

        } // end of TC
    }// end of Main

    private static void makeSet(int n) {
        parent = new int[n][2];
        for (int i = 0; i < parent.length; i++) {
            parent[i][0] = i; // i의 부모는 i
            parent[i][1] = 1; // i집합의 크기는 1;
        }
    }

    private static int union(int a, int b) {
        int x = find(a);
        int y = find(b);

        if (x != y) {
            if (x < y) {
                parent[y][0] = x;
                return parent[x][1] += parent[y][1];
            } else {
                parent[x][0] = y;
                return parent[y][1] += parent[x][1];
            }
        }
        return parent[x][1];

    }

    private static int find(int x) {
        if (x == parent[x][0])
            return x;
        else
            return parent[x][0] = find(parent[x][0]);
    }

}