백준 4195 - 친구 네트워크 (파이썬)

이번 문제는 union-find 알고리즘으로 해결했습니다.
문제의 입력이 숫자가 아닌 문자열이여서 dictionary 자료구조를 사용했습니다.

import sys

input = sys.stdin.readline

def find(x):
    if network[x] != x:
        network[x] = find(network[x])

    return network[x]

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

    if x != y:
        network[y] = x
        num[x] += num[y]

for _ in range(int(input())):
    F = int(input())
    network = dict()
    num = dict()
    
    for __ in range(F):
        a, b = input().split()
        
        if a not in network:
            network[a] = a
            num[a] = 1
        if b not in network:
            network[b] = b
            num[b] = 1

        union(a, b)
        print(num[find(a)])