4195번: 친구 네트워크 (구현, 해시, dict, 분리집합) - Fastcampus

 

• 집합을 부모테이블 (Union-Find 알고리즘)으로 표현할 수 있다

 

www.acmicpc.net/problem/4195

 

4195번: 친구 네트워크

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]


def union(x, y):
    rx = find(x)
    ry = find(y)
    if rx != ry:
        parent[ry] = rx
        count[rx] += count[ry]


# 입력: [('Fred', 'Barney'), ('Barney', 'Betty'), ('Betty', 'Wilma')]
# 출력: [2, 3, 4]
def run(a):
    res = []
    for f1, f2 in a:
        if f1 not in parent:
            parent[f1] = f1
            count[f1] = 1
        if f2 not in parent:
            parent[f2] = f2
            count[f2] = 1
        if find(f1) != find(f2):
            union(f1, f2)
        res.append(count[find(f1)])
    return res


TC = int(input())
for _ in range(TC):
    F = int(input())
    a = [tuple(input().split()) for _ in range(F)]

    parent = {}  # dict
    count = {}
    cnts = run(a)
    print("\n".join(map(str, cnts)))