[알고리즘 문제풀이] 친구 네트워크

문제 제목 : 친구 네트워크

문제 난이도 : 중

문제 유형 : 해시, 집합, 그래프, 분리집합

https://www.acmicpc.net/problem/4195
시간 제한 : 3초
메모리 제한 : 256MB

문제풀이 아이디어

< 소스코드 >

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
        return parent[x]
    else:
        return x
    
    
def union(x, y):
    x = find(x)
    y = find(y)
    
    if x != y:
        parent[y] = x
        number[x] += number[y]
    
test_case = int(input())

for _ in range(test_case):
    parent = dict()
    number = dict()
    
    friend_input = int(input())
    for _ in range(friend_input):
        x, y = input().split(' ')
        
        # 입력값 초기화
        if x not in parent:
            parent[x] = x
            number[x] = 1
        if y not in parent:
            parent[y] = y
            number[y] = 1
            
        union(x, y)
        print(number[find(x)])