[백준 4195번] 친구 네트워크 / union-find 함수

문제 링크

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

4195번: 친구 네트워크

 

풀이 

- union find와 딕셔너리 사용해서 풀이

parent : 이름이 key, 부모 이름이 value 

number : 이름이 key, 속해있는 그래프에 있는 친구 수가 value 

# 부모 찾기 
def find(x):
    if x == parent[x]:
        return x
    parent[x] = find(parent[x])
    return parent[x]

# 두 친구 합치기 
def union(x,y):
    x = find(x)
    y = find(y)
    
    # 같은 그래프에 속해있지 않으면 
    if x != y:
    	# y의 부모를 x로 만들기 
        parent[y] = x
        number[x] += number[y]
        
t = int(input())

for _ in range(t):
    f = int(input())
    
    # 부모 저장 
    parent = dict()
    # 네트워크에 몇 명 있는지 저장 
    number = dict()
    
    for i in range(f):
        x, y = map(str, 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)])