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

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

4195번: 친구 네트워크

1. disjoint-set으로 입력의 왼쪽을 부모로 하는 집합을 만들어준다

2. union에서 부모를 설정할 때 네트워크의 크기도 합쳐서 갱신해준다

3. 출력을 위해 해당 입력의 부모를 찾았을 때 저장한 크기를 return한다

import sys

input = sys.stdin.readline

def get_parent(x):
    if parent[x] == x:
        return x
    p = get_parent(parent[x])
    parent[x] = p
    return p

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

    if x != y:
        parent[y] = x
        s[x] += s[y]

def find_parent(x):
    if parent[x] == x:
        return s[x]
    return find_parent(parent[x])

t = int(input())
for _ in range(t):
    f = int(input())
    parent, s = {}, {}
    for _ in range(f):
        x, y = input().split()

        if x not in parent:
            parent[x] = x
            s[x] = 1
        if y not in parent:
            parent[y] = y
            s[y] = 1

        union(x, y)
        print(find_parent(x))