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

문제

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

접근

1. 각 이름의 부모를 저장하는 자료구조(parents), 집합의 크기를 저장하는 자료구조(count)로 지정한다.
2. parents에 값이 없을 시 count에 1로 지정한다.
3. union-find 알고리즘 실행. 이 때 union을 할 때, count에서 사전순으로 앞선 곳에 집합의 크기를 더해준다. (count[x] += count[y] if x < y)

Code

import sys
from collections import defaultdict


def find(x):
    if parents[x] == x:
        return x
    parents[x] = find(parents[x])
    return parents[x]


def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return
    if x < y:
        parents[y] = x
        count[x] += count[y]
    else:
        parents[x] = y
        count[y] += count[x]


def find_root(x, y):
    if x < y:
        return x, y
    else:
        return y, x


t = int(sys.stdin.readline())
parents = defaultdict(int)
for _ in range(t):
    n = int(sys.stdin.readline())
    parents = defaultdict(int)
    count = defaultdict(int)
    for i in range(1, n + 1):
        a, b = map(str, sys.stdin.readline().split())
        answer = 0

        if not parents[a]:
            parents[a] = a
            count[a] = 1

        if not parents[b]:
            parents[b] = b
            count[b] = 1

        if find(a) != find(b):
            union(a, b)
        print(count[find(a)])

여담

ㅎ..